Steps in the Graph Plan Algorithm
- Expand the Planning Graph: The graph is expanded level by level until it reaches level n where all the goals are present and non-mutex.
- Check for Plan Existence: If the planning graph levels off before all goals are present and non-mutex, the algorithm fails.
- Search for Valid Plan: The algorithm performs a back search from the last level to the initial state to find a sequence of actions leading to the goals without violating mutex constraints.
- Expand if No Valid Plan Found: If no valid plan is found, another level is added and the search is repeated until a plan is found or the graph levels off.
function GRAPHPLAN(problem) returns solution or failure
graph ← INITIAL-PLANNING-GRAPH(problem)
goals ← CONJUCTIONS(problems.GOAL)
loop do
if goals all non-mutex in last level of graph then do
solution ← EXTRACT-SOLUTION(graph, goals, NUMLEVELS(graph)
if solution ≠ failure then return solution
else if NO-SOLUTION-POSSIBLE(graph) then return failure
graph ← EXPAND-GRAPH(graph, problem)
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