CAJ | 학술논문

对智能规划中的常用工具--放松式规划图(relaxed planning graph,简称RPG)的图论性质进行了深入研究.将RPG中的命题层抽取出来,得到一个不包含任何动作的命题关系图(proposition relation graph,简称PRG),发现PRG仍具有RPG的主要规划性质.初步研究结果包括以下4个方面:初始命题集(initial proposition set,简称IPS)的闭出邻集(close out-neighborhoods,简称CON)是放松式规划可达命题集(relaxed reachable proposition set,简称R-RPS);初始状态命题到目标状态命题的最大距离是规划解长度的合理估计;无圈序指出了对应命题被实现的顺序要求;出度或入度为1的结点收缩对应规划中构造的宏动作.上述结果中,前两者说明PRG保留RPG的主要规划性质,后两者可用于建立目标议程或宏动作提取等领域.还提出与上述结论相关的3种算法:从RPG中得到PRG的算法(复杂性为O(mn2),其中,n为RPG的命题数,m为RPG的动作数);约简无圈序算法(复杂性为O(n+m),其中,n为PRG的结点数,m用为PRG的边数);宏动作建议算法(复杂性为O(n2),n为PRG的结点数).
대지능규화중적상용공구--방송식규화도(relaxed planning graph,간칭RPG)적도론성질진행료심입연구.장RPG중적명제층추취출래,득도일개불포함임하동작적명제관계도(proposition relation graph,간칭PRG),발현PRG잉구유RPG적주요규화성질.초보연구결과포괄이하4개방면:초시명제집(initial proposition set,간칭IPS)적폐출린집(close out-neighborhoods,간칭CON)시방송식규화가체명제집(relaxed reachable proposition set,간칭R-RPS);초시상태명제도목표상태명제적최대거리시규화해장도적합리고계;무권서지출료대응명제피실현적순서요구;출도혹입도위1적결점수축대응규화중구조적굉동작.상술결과중,전량자설명PRG보류RPG적주요규화성질,후량자가용우건립목표의정혹굉동작제취등영역.환제출여상술결론상관적3충산법:종RPG중득도PRG적산법(복잡성위O(mn2),기중,n위RPG적명제수,m위RPG적동작수);약간무권서산법(복잡성위O(n+m),기중,n위PRG적결점수,m용위PRG적변수);굉동작건의산법(복잡성위O(n2),n위PRG적결점수).