Planning a Graph for a CAKE Problem
To understand the concept of planning a graph, let’s use the CAKE example. This illustration demonstrates various states and actions to achieve the goal of successfully eating the cake. By examining these states, we can see how actions transition from one state to another to reach the desired outcome.
Initial State (S0)
- Have(Cake): We have the cake.
- ¬Eaten(Cake): The cake has not been eaten yet.
Action Level (A0)
The action level represents possible actions that can transition the state from S0 to the next state. In our example, the available action is:
- Eat(Cake): Represents the action to eat the cake.
Next State (S1)
The next state is determined by the action taken at the action level based on the propositional variables. In the CAKE example, we have four propositional variables in the next state:
- Have(Cake): If no action is performed (no-op), we will still have the cake.
- ¬Have(Cake): If the action Eat(Cake) is performed, we will no longer have the cake.
- Eaten(Cake): If the action Eat(Cake) is performed, the cake will have been eaten.
- ¬Eaten(Cake): If no action is performed (no-op), the cake will still be uneaten.
Performance of Mutual Exclusion in Planning Graph
At state level S1, all literals are obtained by considering any subset of actions at A0. In simple terms, state level S1 holds all possible outcomes after the actions in A0 are considered. In our example, since we only have the Eat(Cake) action at A0, S1 will list all possible outcomes with and without the action being taken.
Mutual Exclusion
Mutual exclusion occurs when a conflict arises between literals, indicating that the two literals cannot occur together. These conflicts are represented by mutex links, which reveal mutually exclusive propositions in S1.
For instance, if we eat the cake, we cannot have the cake at the same time. Thus, Have(Cake) and Eaten(Cake) would be mutually exclusive. The mutex links define the set of states, revealing which combinations of literals are not possible together.
For example:
- If Eat(Cake) is performed, Have(Cake) and ¬Eaten(Cake) cannot be true simultaneously.
- If Eat(Cake) is not performed, ¬Have(Cake) and Eaten(Cake) cannot be true together.
Second Action Level (A1) and State Level (S2)
Continuing from the above example, we introduce two more levels: Action-level (A1) and State-level (S2).
Actions Available at A1 from S1
- Bake(Cake): The precondition for this action is ¬Have(Cake). If ¬Have(Cake) is true in S1, applying Bake(Cake) results in Have(Cake) in S2. This action does not affect the Eaten(Cake) or ¬Eaten(Cake) states.
- Eat(Cake): The precondition for this action is Have(Cake). If Have(Cake) is true in S1, applying Eat(Cake) results in ¬Have(Cake) and Eaten(Cake) in S2.
Planning Graphs in AI
Planning graphs play a vital role in AI planning by visually representing possible states and actions that aid in decision-making. This article explores STRIP-like domains that construct and analyze the compact structure called graph planning. We will also delve into the role of mutual exclusion, providing a suitable example using a graph planning algorithm.
Table of Content
- What is a Planning Graph?
- Levels in Planning Graphs
- Working of Planning Graph
- Mutual Exclusion in Planning Graph
- Planning a Graph for a CAKE Problem
- Steps in the Graph Plan Algorithm
- Properties of Graph Plan
- Conclusion
Contact Us