machine-learning-planning

1. Define the term “Planning” as applied in Artificial Intelligence.

2. List and briefly describe challenges faced by standard searching when you compare it with planning.

3. Mention at least three facts that keep planning agents apart from problem solving agents.

4. What are the differences between planning and problem solving when you consider states, actions and execution.

5. Briefly explain the following terms that are useful when defining a planning system. a. Domain description b. Action Specification c. Goal description d. Preconditions e. Effects

6. How does the classical planning differ from non-classical planning?

7. Briefly explain the two types of planning algorithms.

8. Define the concept of partial order planning in your own words. Give a real-life example of partial order planning.

9. Consider the “Spare Tire Problem” in AI planning. Mention the initial state, goal state and set of actions to have the spare tire in the axle and flat tire in the trunk. Now, write down STRIPS language statements for the above problem.

10. What are the STRIPS statements to solve the “Block World Problem” in the following case. Go through the notebook available online at https://swish.swi-prolog.org/p/STRIPS%20Block%20World.swinb and examine how it is implemented in code level using Prolog.

---

---

1. Define the term “Planning” in the context of Artificial Intelligence. (2 Marks)

Planning in AI refers to the process of devising a sequence of actions (a plan) that transforms an initial state into a desired goal state. It involves reasoning about the current state, available actions, and their effects to achieve specific objectives efficiently. Planning is widely used in robotics, automated systems, and problem-solving scenarios where tasks need to be executed in a structured manner.

Key aspects:

• Initial State: The starting conditions.
• Goal State: The desired outcome.
• Actions: Operations that change the state of the world.
• Constraints: Rules governing valid sequences of actions.

---

2. Explain two challenges that you will have to face if you choose to use standard search algorithms opposed to planning. (4 Marks)

1. State Space Explosion:

   • Standard search algorithms like BFS or DFS explore all possible states in the state space, which can grow exponentially with the number of variables and actions. This makes them computationally expensive and impractical for large problems.
   • In contrast, planning algorithms focus only on relevant actions and states, reducing the search space significantly.

2. Lack of Explicit Representation of Actions:

   • Standard search algorithms treat actions as transitions between states without explicitly modeling their preconditions and effects. This makes it difficult to reason about complex real-world scenarios where actions have constraints.
   • Planning algorithms, such as those using STRIPS, explicitly represent actions with preconditions and postconditions, enabling more structured and logical reasoning.

---

3. Briefly explain two types of planning algorithms. (4 Marks)

1. Forward State-Space Search (Progression Planning):

   • This algorithm starts from the initial state and applies valid actions to progress toward the goal state. It explores the state space by simulating the effects of actions step-by-step.
   • Example: Solving a block-stacking problem by moving blocks from an initial configuration to a desired one.

2. Backward State-Space Search (Regression Planning):

   • This algorithm works backward from the goal state, identifying actions that could lead to it. It determines the necessary preconditions for each action and ensures they are satisfied.
   • Example: Planning how to bake a cake by starting from the goal (cake ready) and working backward to gather ingredients and tools.

---

4. Describe the idea behind “Partial Order Planning”. Also, briefly discuss using an example, how you can use partial order planning to a real-life scenario. (3 Marks)

Partial Order Planning:

• Partial order planning constructs plans by leaving some actions unordered until necessary. Instead of committing to a strict sequence of actions early, it allows flexibility by resolving dependencies only when required.
• This approach avoids unnecessary constraints and enables efficient planning by focusing on critical dependencies.

Example:

• Scenario: Preparing a meal (e.g., spaghetti).
  • Actions: Boil water, cook pasta, heat sauce, set the table.
  • Partial order planning recognizes that boiling water must precede cooking pasta, but heating sauce and setting the table can occur in any order. This flexibility reduces unnecessary sequencing and simplifies the plan.

---

5. Consider the “Spare Tire Problem” in AI planning. Mention the initial state, goal state and set of actions to have the spare tire in the axle and flat tire in the trunk. Now, write down STRIPS language statements for solving the above problem. Make sure to include pre-conditions and post-conditions for each action as well.

Problem Description:

The Spare Tire Problem involves replacing a flat tire on a car with a spare tire. The goal is to have the spare tire mounted on the axle and the flat tire stored in the trunk.

Initial State:

• Flat tire on the axle.
• Spare tire in the trunk.

Goal State:

• Spare tire on the axle.
• Flat tire in the trunk.

Set of Actions:

1. Remove Flat Tire:

   • Preconditions: Flat tire is on the axle.
   • Postconditions: Flat tire is removed, and the axle is empty.

2. Take Out Spare Tire:

   • Preconditions: Spare tire is in the trunk.
   • Postconditions: Spare tire is out of the trunk.

3. Put On Spare Tire:

   • Preconditions: Axle is empty, spare tire is out of the trunk.
   • Postconditions: Spare tire is on the axle.

4. Put Flat Tire in Trunk:

   • Preconditions: Flat tire is removed, trunk has space.
   • Postconditions: Flat tire is in the trunk.

---

STRIPS Language Statements:

// Initial State
Init(FlatTireOnAxle ∧ SpareTireInTrunk)
 
// Goal State
Goal(SpareTireOnAxle ∧ FlatTireInTrunk)
 
// Actions
 
// Action: Remove Flat Tire
Action(RemoveFlatTire,
    Precondition: FlatTireOnAxle,
    Effect: ¬FlatTireOnAxle ∧ FlatTireRemoved ∧ AxleEmpty)
 
// Action: Take Out Spare Tire
Action(TakeOutSpareTire,
    Precondition: SpareTireInTrunk,
    Effect: ¬SpareTireInTrunk ∧ SpareTireOut)
 
// Action: Put On Spare Tire
Action(PutOnSpareTire,
    Precondition: AxleEmpty ∧ SpareTireOut,
    Effect: ¬AxleEmpty ∧ ¬SpareTireOut ∧ SpareTireOnAxle)
 
// Action: Put Flat Tire in Trunk
Action(PutFlatTireInTrunk,
    Precondition: FlatTireRemoved ∧ TrunkHasSpace,
    Effect: ¬FlatTireRemoved ∧ FlatTireInTrunk)

---

Final Answer Summary

1. Planning involves devising a sequence of actions to transform an initial state into a goal state.
2. Challenges of standard search algorithms: state space explosion and lack of explicit action representation.
3. Two types of planning algorithms: forward state-space search and backward state-space search.
4. Partial Order Planning leaves actions unordered until necessary; example: preparing a meal with flexible task ordering.
5. Spare Tire Problem solved using STRIPS includes actions like RemoveFlatTire, TakeOutSpareTire, PutOnSpareTire, and PutFlatTireInTrunk with preconditions and postconditions.

Boxed Final Answers: {See detailed explanations above for each question.}