领域知识优化的蚁群规划算法

Ant swarm planning algorithm optimized by domain knowledge

在智能规划领域的传统图规划算法中,规划解的提取是从规划图的最后一层不断向前提取。提取过程中要不断进行大量状态互斥判断。提取过程中一旦发生失败就要回溯,即使再遇到相同的互斥情形也要重新计算,大量判断互斥的计算被带入主循环搜索过程,极大地影响了搜索效率。将领域知识通过禁忌连接集的形式加入蚁群规划算法中,相邻动作层的很多互斥信息通过禁忌连接集只需计算一次,不带入主循环计算中,可以较好地提升算法的执行效率,实例分析表明这一策略是有效的。

In the study area of automated planning,the planning solution will be extracted from the planning graph,and the extracting way is from the last level to the front by backtracking in an exhaustive way.The plan extracting of the algorithm always consume too much time by this way.In this paper,the domain knowledge will be added into the ant swarm planning algorithm by the form of taboo-connection-set,and the mutex informations can be computed only once because they can be excluded from the main searching cycle.The instance indicates that the tactic is effective.