摘要
如何验证多ａｇｅｎｔ规划是一个非常重要的研究课题，因为该研究关系到规划的求解能否在分布式环境下有效地进行．在本文中，我们讨论了规划的验证方法，给出了压缩集合的生成算法，并给出了该算法的正确性证明．与Ｋａｔｚ等人所提出的算法不同，我们用正向邻接表和逆向邻接表来表示规划链关系Ｄ，用辅助数组来控制所用到的子图（即不是真正的生成子图，但由辅助数组即能看出当前所要处理的子图），提出了避免无用子图产生的方法．我们所给出的算法不论在空间复杂性方面还是在时间复杂性方面都优于Ｋａｔｚ等人所提出的算法．
How to verify plans for multiple agents is a very impotant reseach field, because this reseach has a bearing on an execution of a plan under distributed systems. This paper discusses the method of verifying plans, presents an algorithm for generating compressed sets, and gives correctness proof of the algorithm. It is different from KatZ'S algorithm, the algorithm use adjacency list and inverse adjacency list to represent the plan-link relation D, arrays to control the subgraphs(It isnot generating the subgraphs). Then,a method for avoiding invalid subgraphs is given. From the ponit of view of time complexity and space complexity, the algorithm is better than Katz's.
出处
《计算机学报》
EI
CSCD
北大核心
1996年第3期202-207,共6页
Chinese Journal of Computers
关键词
多agent规划
规划
验证
人工智能
Planning for multiple agents, plan verification, plan link relation.
