Book contents
- Frontmatter
- Contents
- Preface
- Acknowledgements
- 1 Introduction
- 2 Search Spaces
- 3 Blind Search
- 4 Heuristic Search
- 5 Stochastic Local Search
- 6 Algorithm A* and Variations
- 7 Problem Decomposition
- 8 Chess and Other Games
- 9 Automated Planning
- 10 Deduction as Search
- 11 Search in Machine Learning
- 12 Constraint Satisfaction
- Appendix: Algorithm and Pseudocode Conventions
- References
- Index
9 - Automated Planning
Published online by Cambridge University Press: 30 April 2024
- Frontmatter
- Contents
- Preface
- Acknowledgements
- 1 Introduction
- 2 Search Spaces
- 3 Blind Search
- 4 Heuristic Search
- 5 Stochastic Local Search
- 6 Algorithm A* and Variations
- 7 Problem Decomposition
- 8 Chess and Other Games
- 9 Automated Planning
- 10 Deduction as Search
- 11 Search in Machine Learning
- 12 Constraint Satisfaction
- Appendix: Algorithm and Pseudocode Conventions
- References
- Index
Summary
So far in this book we have not thought of plans as explicit representations. True, we have referred to the path from the start node in the state space to the goal node as a plan, but that has been represented as a sequence of states. When we looked at goal trees we could also think of the solution subtree as a plan. Likewise, the strategy found by the SSS* algorithm is also a plan. But even here the intent of the problem solving agent is captured in terms of what state or board position will the player move to.
In this chapter we see problem solving from the perspective of actions. We represent plans explicitly, and the agent goes about the task of synthesizing a plan. At the simplest level, a plan is a sequence of named actions designed to achieve a goal. We begin with planning in the state space and move on to searching in the plan space. We also look at a two stage approach to planning with the algorithms Graphplan and Satplan.
We end with a brief look at some directions in planning in richer domains.
An intelligent agent acts in the world to achieve its goals. Given the state of the world it is in, and given the goals it has, it has to choose an appropriate set of actions. The process of selecting those actions is called planning. Planning is the reasoning side of acting (Ghallab, Nau, and Traverso, 2004). Planning and acting do not happen in isolation. A third process is an integral part of intelligent agency – perceiving. An agent senses the world it is operating in, deliberates upon its goals to produce a plan, and executes the actions in the plan. This is often referred to as the sense–deliberate–act cycle. The entire process may need to be monitored by the agent. Since the world may be changing owing to other agencies, it may even have to modify its plans on the fly.
There has been considerable work on autonomous agents that plan their activity. This became necessary in space applications where communication with Earth takes too long, necessitating autonomy. This was the case with the Mars rovers experiments by NASA, and even ten years after landing on Mars the rover Curiosity is still active.
- Type
- Chapter
- Information
- Search Methods in Artificial Intelligence , pp. 263 - 318Publisher: Cambridge University PressPrint publication year: 2024