高级检索

    基于规划图的蚁群规划算法

    Ant Colony Planning Algorithm Based on Planning Graph

    • 摘要: 图规划是智能规划领域近年来出现的一种重要规划方法,对智能规划的发展起到了很重要的推动作用,图规划算法首先扩展生成规划图,然后通过逐层组合不断回溯的穷举方式进行解提取,这种方式使解提取不仅耗时而且容易陷入局部搜索中.在规划图基础上定义了蚁群智能体,并定义了在规划图上的蚁群搜索方式,提出了蚁群规划算法,使搜索具有较好的全局性和并发性,并具备加速收敛的寻解能力.实验表明,蚁群规划算法在求解一些相对规模较大的规划问题时有更好的优越性.

       

      Abstract: Graphplan is an important algorithm of intelligent planning in recent years. It has promoted great development of intelligent planning. Firstly, the Graphplan algorithm will generate a planning graph by action level expanding and proposition level expanding alternatively. Secondly, a valid plan will be extracted from the planning graph by backtracking in exhaustive way. The plan extracting of the algorithm always consume too much time in this way. And the algorithm is apt to plunge into the local searching. In this paper, a way of plan solution searching by using the ant colony algorithm is given. That is the ACP (ant colony planner) algorithm. In the ant colony algorithm, positive feedback and distributed coordination are used to find the solution path. And the ant colony algorithm even has the characteristic of robustness, thus it has been successfully applied in many applications which are NP-hard problems. The searching of the ACP has the characteristic of global and parallel searching. And ACP has the ability of convergence acceleration in the solution searching. The experiments show that ACP is advantage ous especially in solving the large scale planning problems. To absorb the optimizing technique and the learning technique is a rising way in the study of the intelligence planning. Since the ant colony planning algorithm is just based on the optimizing technique, thus the ant colony planning algorithm is promising to make some better progresses in the study of intelligence planning area by using the ant colony planning method.

       

    /

    返回文章
    返回