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.

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