Constructing Goal Agenda and Macro Actions Using Proposition Relation Graphs in Planning
利用规划命题关系图构建目标议程和宏动作

This paper focuses on graph properties of relaxed planning graph (RPG), a widely-used tool in automated planning. When proposition levels are extracted from RPG, and thus, used to build a proposition relation graph (PRG), it is found that PRG keeps primary planning properties in RPG. Preliminary research results include the following four aspects: The close pth out-neighborhoods (CON) of initial proposition set (IPS) is the relaxed reachable proposition set (R-RPS) in planning; the maximum distance from any proposition in initial state to any proposition in goal states is a reasonable estimation of the plan length; acyclic order in graph indicates that some orders that held corresponding propositions are necessary; contraction of in/out cut-vertex means construction of macro-action is currently being planned. The first and second results show PRG keeps planning properties in RPG, and the third and fourth results can be used in goal agenda building and macro-action construction. Three related algorithms are proposed: PRG in RPG finding algorithm, an O(mn2/4) (n is the number of propositions in RPG, m is the number of actions in RPG) algorithm; acyclic order reduction algorithm, an O(n+m) (n is the number of nodes in PRG, m is the number of edges in PRG) algorithm; macro action suggestion algorithm, an O(n2) (n is the number of nodes in PRG) algorithm.