Types of Planning

Classical planning

• It is the traditional form of AI planning and assumes a static and fully observable environment where all actions are deterministic.

Forward State Space Planning

• Forward State Space Planning (FSSP) is a subset of classical planning. In this approach, the planning system starts from the initial state and explores all possible actions to progress toward the goal. It systematically explores the state space by applying actions and transitions from one state to another until the goal is achieved.

Key Features:

• Exploration Direction: Starts from the initial state and moves forward toward the goal.
• Guarantees: The algorithm is sound and guarantees a solution if one exists.
• Challenges: FSSP can suffer from a large branching factor, meaning the number of potential actions can grow exponentially, leading to high computational costs.

Example: Solving a maze by exploring all possible paths from the starting point.

Backward State Space Planning

• Backward State Space Planning (BSSP) is another variant of classical planning, but it works in reverse. It starts from the goal state and works backward to find the sequence of actions that leads to the initial state. This approach is often more efficient in certain cases where the goal state is clearly defined and specific actions need to be reversed to reach the initial state.

Key Features:

• Exploration Direction: Starts from the goal and works backward toward the initial state.
• Efficiency: BSSP often has a smaller branching factor, making it more computationally efficient.
• Challenges: The algorithm may not always be sound, and inconsistencies might arise, leading to failure in finding a solution.

Example: Planning the steps needed to achieve a goal in chess, working backward from the checkmate position.

Probabilistic Planning

• It is designed to handle environments that contain uncertainty. The AI system must account for the fact that actions may have different possible outcomes with associated probabilities. Probabilistic planning often uses models like Markov Decision Processes (MDPs) or Partially Observable Markov Decision Processes (POMDPs) to manage this uncertainty.

Key Features:

• Handling Uncertainty: Takes into account the likelihood of various outcomes for each action.
• Probabilistic Models: Utilizes models like MDPs and POMDPs for decision-making under uncertainty.
• Challenges: Requires more complex computations due to the need to consider all possible action outcomes and their probabilities.

Example: Autonomous vehicles navigating traffic, where road conditions and other drivers’ behaviours are uncertain.

Reactive Planning

• It is suitable for highly dynamic and unpredictable environments. Rather than following a pre-defined plan, the AI agent continuously reacts to changes in the environment in real-time. This approach doesn’t rely on creating a full plan ahead of time but focuses on immediate responses to the current situation.

Key Features:

• Real-time Adaptation: AI reacts dynamically to changes in the environment.
• No Pre-computed Plan: Focuses on immediate actions rather than long-term planning.
• Challenges: May lack long-term strategy or foresight, focusing only on immediate responses.

Example: A robot avoiding obstacles in an unknown environment or video game AI adapting to player actions.

Hierarchical Task Network (HTN) Planning

• It breaks down complex tasks into simpler, smaller sub-tasks and creates a plan for each sub-task. This hierarchical approach is especially useful for solving large-scale problems where goals can be divided into manageable steps. It often involves decomposing high-level tasks into sequences of lower-level actions.

Key Features:

• Hierarchical Decomposition: Complex tasks are broken down into smaller, more manageable subtasks.
• Structured Approach: Provides a well-structured, layered approach to planning.
• Challenges: Can become inefficient if the hierarchy of sub-goals is too complex or poorly defined.

Advantages:

• Users capability
• Internal flexibility
• Personal reuse and abstraction
• Higher level reasoning adaptability

Example: A robot assembling a product by breaking the task into subtasks like gathering parts, assembling, and testing the product.

Goal stack Planning

• Systematic approach to problem solving
• Simplifies complex tasks into smaller, more manageable steps.
• Works backward from the goal. Takes a goal, identifies sub goals and achieves them all until all goals are achieved.

Key Differences

Feature	Goal Stack Planning	Hierarchical Planning
Approach	Backward reasoning (goal-focused)	Top-down reasoning (task-focused)
Structure	Stack of goals	Hierarchical tree of tasks
Handling Complexity	Struggles with interdependent goals	Efficient for complex, multi-level problems
Focus	Single goal at a time	Multiple goals across different levels
Example Framework	STRIPS	Hierarchical Task Networks (HTN)