论文部分内容阅读
自动规划是人工智能中的一个重要研究领域,在机器人的动作规划,货运码头调度,以及工厂的车间作业调度,现代物流管理以及宇航技术等领域中都有着广泛的应用,因此受到了研究者越来越多的重视。自动规划研究的是通过对周围环境进行认识与分析,根据预定实现的目标,对有限个可供选择的动作及其所提供的资源限制进行推理和评估,综合制定出实现目标的一个动作集的有序序列,即规划解。不确定规划是自动规划中的一个研究分支,最近几年迅速成为了一个新的研究热点。其中的不确定性有动作效果的不确定性,状态的不完全观察,以及扩展性目标等。
群体智能是通过模拟自然界生物群体行为来实现人工智能的一种方法,它强调个体行为的简单性,群体的多样性和全局性,以及优异个体带来的进化性,并且有不断修正和进化的策略。群体智能在很多应用领域中都表现出了较好的寻优性能。如果能将群体智能算法引用到自动规划领域中,是一个预期良好的规划策略。
本文详细介绍了蚁群规划算法的设计及算法,在规划图的基础上引入蚁群算法,提出并定义了基于规划图的路节,路线,提出了适合真伪动作序列的理想命题集,并给出了评价路线优劣的不协调度,通过不协调度的值的变化,向着不协调度越来越小的方向可以引导规划解的搜索。通过禁忌连接集的引入,可以极大地缩减搜索空间。另外,作为一个启发式公式,评价蚁群路线的不协调度可以方便地融入一些领域知识,从而进一步提高算法的效率。并通过实例分析验证了算法的有效性和可行性。
在传统规划问题上,寻找规划解都是NP,甚至NP完全的问题,如果动作的执行效果带有不确定性,如在Markov决策过程的规划问题中,规划的求解将会更加困难,现有的Markov决策过程的规划算法往往用一个整体状态节点来描述某个动作的实际执行效果,试图回避状态内部的复杂性,而现实中的大量动作往往都会产生多个命题效果,对应多个命题节点。为了能够处理和解决这个问题,本文提出了映像动作,映像路节和映像规划图等概念,并在其基础上提出了Markov决策过程的蚁群规划算法,从而解决了这一问题。并且证明了算法得到的解,即使在不确定的执行环境下,也具有不低于一定概率的可靠性。