7
$\begingroup$

I'm studying Artificial Intelligence. A Modern Approach, Stuart Russell, Peter Norvig, specifically about search and planning arguments.

I don't understand the difference between the two terms. I was more confused when I saw that some search problems can be determined in planning way. My professor explained to me in a confusing way that the real difference on the search is that it uses an heuristic function, but my book says that planning use a heuristic too, for relaxing problem (in cap. 10.2.3).

I read this page that says in a certain way what I'm saying.

Is planning and search the problem? If not, what are the differences and how are these problems related?

$\endgroup$
0
0
$\begingroup$

What is planning?

Planning (aka automated planning or AI planning) is the process of searching for a plan, which is a sequence of actions that bring the agent/world from an initial state to one or more goal states, or a policy, which a function from states to actions (or probability distributions over actions). Planning is not just the use of a search algorithm (e.g. a state-space search algorithm, such as A*) to find the plan, but planning also involves the modelling of a problem by describing it in some way, e.g. with an action language, such as PDDL or ADL, or even with propositional logic.

There are different planning problems, such as

  • classical planning
  • planning in Markov Decision Processes (which are mathematical models that describe stochastic environments/problems, i.e. environments where an action $a$ may not always lead to the same outcome)
  • temporal planning (i.e. when multiple actions can be taken at the same time and/or their duration may be different/variable)
  • hierarchical vs non-hierarchical planning

There are different planning approaches, such as

  • planning by state-space search (with or without heuristics), i.e. formulate the planning problem so that you can apply a state-space search algorithm (examples of state-space search algorithms are A*, IDA*, WA*, DFS or BFS); this is probably the approach to planning that makes people confuse planning with search (which typically implicitly refers to state-space search)

  • planning by SAT, i.e. formulate the planning problem so that you can you a SAT solver to solve it (e.g. SATPLAN)

  • planning by solving constraint satisfaction problems (similar to SAT)

  • planning by "symbolic" search methods (such as Binary Decision Diagrams)

There are many different planning algorithms or planners (of course, each of these corresponds to some approach or is used to solve a particular planning problem), such as

  • policy iteration in the context of Markov decision processes
  • GraphPlan
  • STRIPS (which stands for Stanford Research Institute Problem Solver, but note that STRIPS also and maybe more commonly refers to the corresponding description language used to describe the planning problem)

What is search?

In the context of AI, when people use the word search, they can either implicitly refer to state-space search (with algorithms like A*) or, more vaguely/generally, to any type of search, e.g. gradient descent can also be viewed as a search algorithm, typically, in a continuous state space (rather than discrete state space), e.g. the space of real-valued vectors of parameters for a certain model (e.g. a neural network).

What is the difference between planning and search?

The difference should more or less be clear from my first paragraph above that describes planning: search is used for planning, but the planning process/study also includes other things, such as describing the problem with an action language, such as PDDL. You can also view planning as an application of search algorithms of different types. In any case, planning is about searching for plans or policies. You should probably check this course for more info. This definition of (automated) planning is consistent with our usual notion of planning.

$\endgroup$
-1
$\begingroup$

Often terminology is vague and if this will be a test item for school I would circle back with teacher with my response before accepting it.

They key difference is prior knowledge.

Search - when one searches they explore without prior knowledge. This would likely be a stochastic process of trial and error. There is no expectation about state transitions. Example is exploring an abandoned house. You have no idea what you'll find next.

Plan - you have a model of state transitions and can make predictions. One step or multi step prediction capabilities allow you to predict an outcome and therefore choose an outcome from several options.

$\endgroup$
5
  • $\begingroup$ You can search with prior knowledge. This is typically done with heuristics and this is known as informed search. $\endgroup$ – nbro Mar 19 at 9:02
  • $\begingroup$ Your over thinking this person's question and not directly answering it at the level he is asking it. My answer was purposely simplistic because the question is simplistic $\endgroup$ – cagney Mar 19 at 16:28
  • $\begingroup$ But it's wrong to say that search cannot use domain knowledge. A* (a search algorithm) is an informed search algorithm that can use domain knowledge. I'm not overthinking anything. My answer is based on my knowledge of the topic and the info that I've found after having researched the topic even further for a few hours. $\endgroup$ – nbro Mar 19 at 16:32
  • $\begingroup$ Although your answer has correct information and mine leaves out lots of information I think that the person asking it needed a simple answer. If you boiled down your answer into a single qualitative description of the difference im curious what it would be. $\endgroup$ – cagney Mar 19 at 16:37
  • $\begingroup$ The main difference between planning and search is given in my first paragraph. In other words, I would say that planning is an application of search (or applied search) or a "specialized" search in order to achieve a goal starting from some initial conditions. One thing that needs to be super clear is: planning definitely involves some notion of "search", but (almost) any problem-solving technique involves search anyway (maybe apart from random guessing). $\endgroup$ – nbro Mar 19 at 16:39

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.