This Title All WIREs
How to cite this WIREs title:
WIREs Cogn Sci
Impact Factor: 3.476

Computational models of planning

Full article on Wiley Online Library:   HTML PDF

Can't access this content? Tell your librarian.

Abstract The selection of the action to do next is one of the central problems faced by autonomous agents. Natural and artificial systems address this problem in various ways: action responses can be hardwired, they can be learned, or they can be computed from a model of the situation, the actions, and the goals. Planning is the model‐based approach to action selection and a fundamental ingredient of intelligent behavior in both humans and machines. Planning, however, is computationally hard as the consideration of all possible courses of action is not computationally feasible. The problem has been addressed by research in Artificial Intelligence that in recent years has uncovered simple but powerful computational principles that make planning feasible. The principles take the form of domain‐independent methods for computing heuristics or appraisals that enable the effective generation of goal‐directed behavior even over huge spaces. In this paper, we look at several planning models, at methods that have been shown to scale up to large problems, and at what these methods may suggest about the human mind. WIREs Cogn Sci 2013, 4:341–356. doi: 10.1002/wcs.1233 This article is categorized under: Computer Science > Artificial Intelligence

The graph corresponding to a simple planning problem involving three blocks with initial and goal situations as shown. The actions allow moving a clear block on top of another clear block or to the table. The size of the complete graph for this domain is exponential in the number of blocks. A plan for the problem is shown by the path in red.

[ Normal View | Magnified View ]

Top: Problem where visual‐marker (circle on the lower left) must be placed on top of a green block by just observing what's on the marked cell. Down: Finite‐state controller obtained with a classical planner from suitable translation. The controller has two states, the initial state q0 and the state q1. An edge qq′ with label o/a means to do the action a when observing o in the state q, and to move then to the state q′. The controller shown solves the problem, and any variation of it resulting from changes in the number or configuration of blocks.

[ Normal View | Magnified View ]

A fragment of the graph corresponding to the blocks problem with the automatically derived heuristic values next to some of the nodes. The heuristic values are computed in low polynomial time and provide the search with a sense of direction. The instance can actually be solved without any search by just performing in each state the action that leads to the node with a lower heuristic value (closer to the goal). The resulting plan is shown in red; helpful actions are shown in blue.

[ Normal View | Magnified View ]

The sliding 15‐puzzle where the goal is to get to a configuration where the tiles are ordered by number with the empty square last. The actions allowed are those that slide a tile into the empty square. While the problem is not simple, the heuristic that sums the horizontal and vertical distances of each tile to its target position is simple to compute and provides an informative estimate of the number of steps to the goal. In planning, heuristic functions are obtained automatically from the problem representation.

[ Normal View | Magnified View ]

Related Articles

Cognitive Science: Overviews

Browse by Topic

Computer Science and Robotics > Artificial Intelligence

Access to this WIREs title is by subscription only.

Recommend to Your
Librarian Now!

The latest WIREs articles in your inbox

Sign Up for Article Alerts