What is the difference between search and planning

Question

In artificial intelligence, I am now reading about planning. But as a naive to AI, I couldn't get the point they are insisting on the 'difference between planning and search'.

I have procedural programming knowledge like C/C++, and I can do search based on data structures.

And I couldn't understand the example of Buy(ISBN0123654789) and Have(ISBN0123456789) given in 'Artificial Intelligence: A modern approach - Stuart Russell' in which they gave, search a ten digit ISBN number will take 10 billion actions.

My question is about how searching a book will need 10 billion actions, but planning doesn't.

Finery

See this answer that I gave. – Zeeland

Answer 1

Russell and Norvig are not saying that searching and planning are different things. In fact, in the section I think you're taking about (in Chapter 10 of the Blue Edition) they say exactly the opposite: A planning problem can be reduced to a search problem.

But, the plan expressed as a search may have a monstrously large search space. In the book example, there are 10^10 different possible actions, and with an uninformed search technique the computer does not "know" that buy(x) results in have(x) even though this is trivially obvious to a human being. Thus, even the search space of single-action plans is huge. That sounds stupid, but it is the definition of uninformed search.

As a result, planning algorithms that actually work require some algorithmic and/or heuristic cleverness, which the rest of that chapter goes on to describe. In the book example, the improved search reasons backwards from the goal of have(x), performs some first-order-logic schema listing using the buy(x) vs have(x) connection and derives the correct action.

As a side note, I am a great fan of Russell and Norvig's book, and their work in general. But I found the planning chapters to be a little bit weak. Professors Lozano-Perez and Kaelbling have their lecture notes from a class using a previous edition of the book online. Their notes are very detailed, with examples. I found them to be an excellent supplement when I was studying this material:

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-825-techniques-in-artificial-intelligence-sma-5504-fall-2002/index.htm

Pincers

Answer 2

I'm not familiar w/ the specific example you cite, but I'll try anyway.

Search is an almost totally generic construct: there is a space of possibilities, and you want to locate one, but you have to find it by inspecting a (not necessarily proper) subset. There are all manner of details as to the specific search problem (i.e. what is the space, how are you allowed to query it, etc.) and particular search algorithm (most importantly, how you organize which parts of the space you query in what order). Pretty much ANY problem can be posed as a search problem (what's the space of possibilities, and how do you tell which is a desired one), which is why it plays such a prominent place in AI.

Planning is a particular kind of search: it is a search through the space of action sequences (or more generally, partial orders) for a plan that satisfies some criteria. That doesn't mean it has to be IMPLEMENTED as a search (just as some problems which could be solved using search can be solved with other means), but the problem can be described that way.

Saying that finding a book by its ISBN will take 10 billion actions suggests checking an ISBN is one of the actions (as there are that many possible ISBNs), but somehow planning (i.e. finding an appropriate action sequence) will result in fewer actions (because you then won't need to inspect all of the ISBNs?). But without details of the problem, I can't say how reasonable that claim is.

Ritaritardando

The ISBN example is misused. Russell and Norvig use it to explain the difference between Forward and Backward search. – Rincon

Answer 3

Planning can make use of Regression Search i.e. start with the goal state and form a plan to reach the initial state.

For your book example, if you start with PRECONDITION: buy(B), ISBN(B) then you may have million possibilities to look out(since there are a million ISBN numbers), but you want to "plan" how you may reach the goal state and not just "search"

Planning gives you the sequence of actions you need to reach the goal state. Searching is not concerned with "actions"

Source: Udacity AI course and AIMA: Russel, Norvig

Telemeter

What happens to the concept of bi-directional search? It allows us to do both forward and backward search simultaneously. Talking about the first paragraph. – Strawberry

Answer 4

The main difference between search and planning is the representation of states In search, states are represented as a single entity (which may be quite a complex object, but its internal structure is not used by the search algorithm) In planning, states have structured representations (collections of properties) which are used by the planning algorithm

Mismatch

Answer 5

To keep it short, the differences are:

• Search is done in parallel and a highly disreputable operation

• Representation of states:

  • Search-states are represented as a single entity of which their internal structure is not used
  • Planning-states have structured representation that are used by the planning algorithm

• Planning can make use of Regression Search

  • i.e. start with goal and form a plan from initial state

Interstratify