Planning in State Space Search

Planning in State Space Search

Problem solving in AI may be characterized as a systematic search through a range of possible actions in order to reach some predefined goal or solution. The problem solving agents decide what to do by finding sequence of action that lead to desirable states. The simplest agents which have been described below are the reflex and goal based agents. The reflex agents use direct mapping from states to actions and are unsuitable for very large mappings. Problem solving agents find action sequence that lead to desirable state.

A state space is represented by four components like steps involved in a problem solving process, the start state of the problem and the corresponding goal state. Search algorithms should track the paths from the start node to the goal node because these paths contain a series of operations that lead to the solution of the problem. A programmer should analyze and predict the behaviour of search algorithms to successfully designed and implement them in a proper manner. The problems can be characterized as spaces consisting of a set of states and a set of operators that map from one state to another state. The states may be distinguished as containing one of the following: one or more initial or starting states, a number of intermediate states and one or more goal states. A sequence of operators that map an initial state to a goal state will provide the solution to a problem. A best solution is one that requires the fewest no. of operations while mapping from an initial state to the goal state. The amount of time and memory space required to complete the mapping measures the performance of a particular solution method. The state space search can be in forward and backward direction. The forward state space planning is also known as progression planning in which searching always takes place in forward direction. In backward search, it finds only the relevant actions. An agent with several immediate options of unknown values can decide what to do by first examining the different possible sequences of actions that lead to states of known values and then choosing the best one.

A state space search can be searched in two directions like from the inputs towards the goal or from the goals towards the inputs. In data driven search, one starts with the given facts of a problem and uses a set of legal moves or rules to change the states. This process is continued until it generates a path that satisfies the goal condition. In goal driven search, first determine the rules or legal moves that can be used to generate the goal and identifies the condition that can be applied to use these rules. These conditions form the new goals or sub goals for the search. One must continue the search process by working backwards through successive sub goals until it returns of moves or rules leading from the data to a goal, even if it performs this process backwards. Data driven search is suggested if one is provided with almost all the data at the time of formulation of the problem statement.

Data driven search uses the knowledge and constraints present in the given data of a problem to guide the search along a path. The main work in the area of search strategies is to find the correct search performance measures like time complexity, space complexity, completeness and optimality help to judge the fitness of a particular search algorithm.