1
$\begingroup$

I'm studying artificial intelligence following the Russell & Norvig book. We did a search and planning part that for me is the same (at least on the representation). I'd like to know what is the difference between these two techniques, but I couldn't find it.

Looking online I found this resource: Planning and Search, where it says: "The main difference between search and planning is the representation of states."

Is the difference between these two techniques limited to the representation?

$\endgroup$
1
$\begingroup$

Short answer is "Yes".

Long answer is "No":

As far as I am concerned the difference is limited to a specific author/lecture: (to the best of my understanding of the slides) The author of the linked slides does not want to refer to "search" as a technique like planning, but rather as a general procedure.

Planning is the process of finding a set of (valid) actions that transform an initial state (set of properties) to a goal state. Such a problem can be represented by a state space graph, where each node defines a complete world state (i.e. a set of properties). Two nodes are connected if there exists a valid action transforming one state into another.

  • "Search" is the general procedure of finding a solution by searching the problem space. In this case it is the process of iterating a state space graph starting at the initial node, trying to find a path to the goal node, i.e., using DFS. The search problem is given an (perhaps implicit) representation of the graph and is not concerned about internal properties of nodes.
  • A non-search "Planning" algorithm on the other side may make use of the logical properties of the states to iterate the state space graph.

However, I would like to note that most "Planning" algorithms do use some kind of search procedure on the state space graph, significantly improving the search using planning-heuristics: Consider the graph given on slide 4 (of the referenced link). The complete graph represents the planning problem. The search "only sees" nodes and edges. A DFS would simply iterate all possible paths until a solution is found. A heuristic (planning algorithm) may use additional relations between properties (i.e. getting milk implies going to the supermarket first).


Informal definition of plan: the solution to a planning problem. A sequence of actions that translate the initial (world) state into the goal state.

In terms of the (graph) search this would be a list of edges to traverse. If there exists a valid plan, then there exists a path in the graph.


(this may be a little out of scope) Since planning is in general PSPACE-complete naive search algorithms perform exceptionally bad on many instances. Common heuristics/techniques used in planning are based on the relaxation of the state space graph, i.e., by relaxing preconditions or effects (resulting in easier problems; in P, or NP) which can be solved "easily". If you are interested in planning that is somewhat separated from "search" you might wan to take a look at hierarchical task networks (HTN) which is basically planning with additional domain knowledge.

$\endgroup$
  • $\begingroup$ If (strlen("yes")>strlen("no")) printf("Waaaait a minute!\n"); \\ ;-) $\endgroup$ – David Richerby Jun 21 at 13:33
  • $\begingroup$ to sum up I could say that a schedule is a sequence of actions that could lead to the goal, while in a search we have a series of actions, and one of this could be on goal? $\endgroup$ – theantomc Jun 21 at 14:45
  • $\begingroup$ I would not mix up terms here: a schedule relates to scheduling problems which is something completely different. To sum it up: In planning you try to find a "plan", which is a sequence of (applicable) actions leading to the goal. A (graph) search is a possible procedure to find such a plan. $\endgroup$ – Fleeep Jun 21 at 14:59
  • $\begingroup$ So by definition, the plan has always a goal or goals? Instead, the graph search can be failed, right? @Fleeep $\endgroup$ – theantomc Jun 22 at 13:34
  • $\begingroup$ Added that to the answer. If graph search fails then there is no plan. $\endgroup$ – Fleeep Jun 24 at 6:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.