He who every morning plans the transaction of the day and follows out that plan, carries a thread that will guide him through the maze of the most busy life. But where no plan is laid, where the disposal of time is surrendered merely to the chance of incidence, chaos will soon reign.

– Victor Hugo (1802–1885)

Planning is the process of finding a sequence of actions to achieve a goal. Because an agent does not usually achieve its goals in one step, what it should do at any time depends on what it will do in the future. What it will do in the future depends on the state it is in, which, in turn, depends on what it has done in the past. This chapter presents three representation of actions and their effects, and four offline algorithms for an agent to find a plan to achieve its goals from a given state.

This chapter makes the following simplifying assumptions:

• •

  There is a single agent.

• •

  The agent’s actions are deterministic and the agent can predict the consequences of its actions.

• •

  There are no exogenous events beyond the control of the agent that change the state of the environment.

• •

  The environment is fully observable; thus, the agent can observe the current state of the environment.

• •

  Time progresses discretely from one state to the next.

• •

  Goals are predicates of states that must be achieved.

Some of these assumptions are relaxed in the following chapters.