论文摘要
随着人工智能的快速发展,智能无人平台逐渐向小型化和智能化转变,多无人平台的高效协同将在未来的信息化战场、太空探索、抢险救援等领域有着广泛而深入的应用。在该问题背景下,当目标任务随机到达,目标之间存在强偏序约束,且目标任务的执行时间和执行的成功概率都具有时间相关不确定时,为了实现多无人平台之间的在线协同,满足在线计划过程中的时效性,需要设计高效的在线规划与调度方法,实时的生成执行计划,并优化调度相关的无人平台去执行。本文以此为研究目的,主要讨论:如何建立智能规划与优化调度相结合的在线计划系统;如何利用智能规划语言PDDL进行计划问题的描述与建模,描述无人平台之间的协同交互关系;如何在目标任务之间存在强偏序约束的情况下快速搜索执行目标任务的行动序列;以及如何在时间相关不确定环境下,针对规划过程生成的行动序列进行行动的起止时间推理和无人平台的在线优化调度,获得全局较优计划方案。主要工作如下:(1)建立了离线状态下基于运筹学方法的问题模型,并讨论了在线计划框架和基于PDDL的规划问题建模。文中通过基于运筹学方法的问题建模,对本文研究问题的特点和问题求解的复杂度进行了详细讨论;然后,根据智能规划和运筹学中优化调度的各自特点,设计了智能规划与优化调度相结合的在线计划系统框架。文中以单舰的不同武器平台自动协同防空为例,讨论了针对某一给定规划问题的PDDL描述与建模方法,为后续的智能规划搜索算法提供模型基础,并以该案例为背景,讨论了舰艇防空的在线计划系统的运行流程,设计开发了舰艇防空的在线计划仿真实验平台。(2)提出了规划过程中的死锁检测算法和多步前向搜索算法,用于解决初始状态下目标任务之间存在强偏序约束的规划问题。在该类问题中,目标任务的实现顺序必须满足初始状态下存在的偏序约束,搜索过程一旦违背任何偏序约束都会导致搜索过程进入死锁。现有的规划算法在规划解的搜索过程中,不能准确发现该类问题中目标任务之间的强偏序约束关系,从而无法快速获得规划解。本文针对这一问题,构建了基于目标实现图的死锁检测算法,该算法能快速预测搜索过程中因违背目标任务之间的强偏序约束而导致的显性和隐性死锁,从而引导多步前向搜索过程快速向目标状态逼近,并快速返回规划解。文中对算法的复杂度、充分性和适用领域进行了讨论,并通过三个不同领域的规划问题将本文算法和历年的冠军规划器进行了实验对比,验证了本文算法在解决该类问题时的充分性和有效性。(3)提出并解决了因相斥目标实现行动导致的强偏序约束规划问题。在该类规划问题的初始状态下,目标任务之间不存在任何强偏序约束。但是随着规划过程的进行,由于相斥目标实现行动的存在,对某一目标任务实现过程中的目标实现行动的选择不当,可能给后续的规划过程中引入目标实现顺序的强偏序约束。文中对该类问题的性质进行了分析,并从理论和实验上论证了该类问题的复杂性。通过对前面提出的死锁检测算法的进一步拓展,提出了以相斥目标实现行动集为启发式函数的多步前向搜索算法,并对算法的复杂度、算法求解该类问题的充分性和算法适合的问题特点进行了讨论。而且,文中构造了以编队舰艇防空为背景的相斥目标实现行动导致的强偏序约束规划问题,通过与历年的冠军自动规划器相比较,充分显示了现有规划算法在求解这一新的规划问题时存在的不足,以及本文算法在求解该类规划问题时的有效性。(4)研究了基于重计划的在线计划优化方法。在线过程中,由于目标任务的连续随机到达和计划执行结果的不确定性,当前的计划策略不可避免的存在“短视”现象。在对未来目标任务到达分布未知的情况下,为了能够获得全局较优解,文中设计了基于重计划的在线规划与调度策略,对当前已经生成但还未执行的目标任务的计划方案进行在线优化处理,以获得全局较优解。重计划过程具备实时性,充分考虑算法耗时对计划过程的影响、行动的时间推理、以及无人平台之间的最优化协同调度。文中以单舰的不同武器平台的协同防空为仿真案例,设计开发了仿真实验平台,验证了重计划的在线优化方法在获取全局较优解时的有效性,且用于重计划的时间越长,对全局解的优化程度越高。(5)研究了基于分散式马尔科夫决策过程的在线计划方法。该研究主要针对能准确估计未来目标任务到达的概率分布,目标任务的执行持续时间和计划执行的成功概率都具有时间相关不确定性,以及不允许进行重计划情况下的在线计划方法。针对每一个到达的目标任务,既要考虑调度无人平台以最大期望完成该目标任务,又要确保该决策造成的潜在机会损失最小,以获得计划过程的全局较优解。文中采用基于分散式马尔科夫决策过程的在线计划模型,模型的收益函数考虑了当前的决策收益和未来潜在的机会损失,并以编队的舰艇防空为案例,设计开发了仿真实验平台,通过仿真实验论证了考虑潜在机会损失的计划过程能返回全局较优计划方案。