Motivations of studying planning:
- Need for information processing tools that provide affordable and efficient planning resources (Practice)
- Planning is an important component of rational behavior. One of the important purposes of AI (Theory)
First Intuitions on Planning
Planning is the reasoning side of acting. It is an abstract, explicit deliberation process that chooses and organizes actions by anticipating their expected outcomes. This deliberation aims at achieving as best as possible some presented objectives. Automated planning is an area of Artificial Intelligence (AI) that studies this deliberation process computationally.
When we don’t need planning:
When the purpose of an action is immediate given our knowledge of that action, or when we perform well-trained behaviors for which we have presented plans, or when the course of an action can be freely adapted while acting, then we usually act and adapt our actions without explicitly planning them.
Reactive vs. Deliberative agents:
Reactive agents simply retrieve pre-set behaviors similar to reflexes without maintaining any internal state. On the other hand, deliberative agents behave more like they are thinking, by searching through a space of behaviors, maintaining internal state, and predicting the effects of actions. Although the line between reactive and deliberative agents can be somewhat blurry, an agent with no internal state is certainly reactive, and one which bases its actions on the predicted actions of other agents is deliberative.
Forms of Planning:
- Path and motion planning:
Is concerned with the synthesis of a geometric path from a starting position in space to a goal and of a control trajectory along that path that specifies the state variables in the configuration space of a mobile system, such as a truck, a mechanical arm, a robot, or a virtual character.
- Perception planning:
Is concerned with plans involving sensing actions for gathering information. Perception planning addresses questions such as which information is needed and when it is needed, where to look for it, which sensors are most adequate for this particular task, and how to use them.
- Navigation planning:
Combines the two previous problems of motion and perception planning in order to reach a goal or to explore an area.
- Manipulation planning:
Is concerned with handling objects, e.g., to build assemblies.
- Communication Planning:
Arises in dialog and in cooperation problems between several agents, human or artificial. It addresses issues such as when and how to query needed information and which feedback should be provided.
Domain Specific Approaches
Disadvantages of domain specific approaches:
- They require external understanding of general planning forms.
- It is more costly to address each planning problem anew instead of relying on and adapting some general tools.
- Domain-specific approaches are not satisfactory for studying and designing an autonomous intelligent machine.
For all these reasons, automated planning is interested in domain-independent general approaches to planning.
Models used in domain-independent planning:
- Project planning:
In which models of actions are reduced mainly to temporal and precedence constraints, e.g., the earliest and latest start times of an action or its latency with respect to another action
- Scheduling and resource allocation:
In which the action models include the above types of constraints plus constraints on the resources to be used by each action.
- Plan Synthesis:
In which the action models enrich the precedent models with the conditions needed for the applicability of an action and the effects of the action on the state of the world.
Conceptual Model for Planning
A conceptual model is a simple theoretical device for describing the main elements of a problem.
Since planning is concerned with choosing and organizing actions for changing the state of a system, a conceptual model for planning requires a general model for a dynamic system.
We’ll use state-transition system (also called discrete-event systems) to describe the conceptual model of the planning.
Fig. 1: A simple conceptual model for planning.
A plan is a structure that gives the appropriate actions that leads you to the objective. The objective can be specified in several different ways:
- Specifying goal state or set of goal states.
- More generally, the objective is to satisfy some condition over the sequence of states followed by the system.
- An alternative specification is through a utility function attached to states, with penalties and rewards. The goal is to optimize some compound function of these utilities (e.g., sum or maximum) over the sequence of states followed by the system.
- Another alternative is to specify the objective as tasks that the system should perform. These tasks can be defined recursively as sets of actions and other tasks.
A more realistic model interleaves planning and acting, with plan supervision, plan revision, and replanning mechanisms. There is a need for a closed loop between the planner and the controller (Figure 1). The latter returns to the planner the execution status of the plan to enable dynamic planning.
Fig2: A conceptual model for dynamic planning.
Fully observable systems are systems were the controller is able to know all information about the system. Otherwise it’s called partially observable.
The restricted conceptual model plan is unconditional, and the controller executing the plan is an open-loop controller, i.e., it does not get any feedback about the state of the system.
Restricted Planning Model:
- Finite system.
- Fully observable.
- Restricted goals.
- Sequential plan.
- Implicit time.
- Offline planning.
Conformant planning deals with nondeterministic and partially observable systems.