计算机论文哪里有?本文的研究内容围绕如何优化行为树并行执行任务同步与资源调度展开,在经典行为树的基础上,提出强同步与弱同步并行控制节点和资源控制节点来优化行为树并行任务执行,并且设计了仿真实验对算法效果进行验证。
第一章 前言
1.2 国内外研究现状
行为树起源于计算机游戏行业,主要用来对游戏的非玩家角色的行为进行建模。行为树的早期重要思想主要来自游戏设计社区的博客,其发展的重要里程碑是在Michael等人提出一种基于反应式的行为语言(A Behavior Language,ABL[7])来处理具有交互能力的游戏角色行为,其中采用大量的行为树模块化设计思想。随着这些主要的设计思想不断地发展,关于行为树的正式理论研究发表于TCIAIG期刊的论文《Dynamic expansion of behavior trees》,Puga[8]等人提出采用基于案例推理(Case Based Reasoning,CBR)的技术来设定游戏中非玩家角色的行为,通过行为树对非游戏玩家的行为进行建模。随着游戏人工智能的迅速发展,也带动了行为树的相关理论不断地成熟与完善。相比于早期游戏领域所使用的有限状态机,行为树的出现不仅受到游戏人工智能领域的称赞,而且因其模块化、可重用性与可读性受到机器人控制系统领域专家的欢迎。例如,早期Ogren[9]等人提出采用行为树体系结构来模块化设计无人机控制系统,这也是首次将行为树从游戏人工智能引入到机器人领域相关研究,并且系统的介绍的行为树基础理论。至此行为树与机器人技术的研究联系更加的紧密。
行为树在当今的游戏领域应用广泛,包括在实时战略游戏(Real Time Strategy Game,RTS)、第一人称射击游戏(First Person Shooting Game,FTS)、平台游戏以及大型地剧情交互式游戏等有着出色表现。Weber[10]提出通过专家系统观察到的信息,然后总结来自专家行为示例的大量信息,构建行为树用来作为《星际争霸》中玩家的战略执行系统。Johansson[11]等人提出将时间折扣、风险感知和计划等引入到行为树,通过这三种因素来选择最优运行的行为树子节点,来决定游戏角色的决策范围,并在第一人称射击游戏进行实验验证。在[12]中采用无模型的自动规划(Automatic Planning,AP)框架,使用遗传规划(Genetic Programming,GP)来推导智能体在未知环境中实现给定目标的最优BT,并且基于开源Mario AI基准对所提框架进行验证。
第三章 行为树并行执行的任务同步研究
3.1 行为树并行执行的相关工作
3.1.1 行为树的并行研究
行为树中的并行控制节点在实际应用中使用较少,传统的BT并行机制的局限性之一是要求并行任务是独立的,二是并行任务执行时可能会遇到类似计算机并行程序中饥饿、死锁、竞争条件等问题,因此在使用并行控制节点比采用行为树其控制节点更少。然而,在许多实际应用中,并行任务之间存在着内在的联系,这些任务通过合理的协作执行来提高任务的执行效率。例如,当机器人试图抓取桌子上的物体时,机器人需要进行视觉感知物体与机械臂的物体抓取的任务同步执行,才能够成功抓取物体的任务。一般采用的方法是先对目标物体进行视觉感知,然后再执行抓取任务,相对并行地执行效率较慢。
目前针对行为树并行研究已有初步进展。文献[44]中使用并行控制节点来监控用户请求并执行相应的任务,由于用户定义的任务是互斥的。因此,行为树并行节点下的任务都在其自己的子空间执行。
反应式行为语言[7]最初是为对话游戏Façade设计的,其中使用大量的并行控制节点,它能够处理多个规模的计划和行动,特别是实时战略游戏。并行执行子任务,并通过定义固定的优先级顺序来解决多个并发任务之间的冲突。然而,这样做可能不利于行为树的模块化,并可能引发类似计算机并发进程中饥饿情况。
第五章 行为树并行执行任务同步与资源调度的仿真和效果评估
5.1 仿真环境配置
本节主要介绍仿真环境的具体配置情况,包括使用的计算机系统、机器人操作系统(Robot Operating System,ROS)、Gazebo可视化物理模拟器和ROS行为树函数库ROS-Behavior-Tree开源项目。
5.1.1 实验平台介绍
本文采用的实验平台基于Ubuntu16.04系统的台式机,CPU为Corei7处理器,CPU频率为3.0GHZ,运行内存为16.0GB。
本文使用的是开源机器人操作系统ROS。2010年由Willow Garage公司发布,很快吸引了一批机器人研究领域的专家学者展开了对机器人操作系统的学习应用,经历了十多年的发展,已经更新到ROS Noetic第十三代版本。本文使用的是与Ubuntu16.04系统相对应地ROS Kinetic Kame版本,并且该版本较为稳定。ROS为用户提供操作系统应用的服务基本功能,包含硬件抽象具体描述、底层驱动程序控制管理、常用的函数调用、应用程序间的消息传递以及包管理。它也提供用来快速获取、编译、编写以及在多台计算机运行的工具程序和库函数。
ROS具有以下特点:首先ROS采用点对点的设计方式,通过服务和节点管理器等机制,用于分散缓解因语音识别和计算机视觉等带来的实时计算压力。系统能够布置在多个机器人实现机器人协同工作。在ROS系统中可以使用多种编程语言其中包括主流的Java、C++和Python等编程语言。ROS采用了一种语言中立的接口定义语言来实现各模块之间的消息传送。采用ROS作为机器人的操作系统能够将系统模块化易于管理,各模块中的代码可以单独编译,编译中使用的CMake工具使简化的概念易于实现。
5.2 行为树并行执行的任务同步仿真实验
本节主要是对第三章提出的强同步并行与弱同步并行执行算法结合具体的仿真实验进行验证。
仿真实验场景是在一块无任何障碍100*100区域开展,如图5.1所示,地图中包含智能ROS机器人以及可运动的黄色小球。仿真实验主要是机器人识别黄色小球进行保持一定距离的跟随来验证所提出的算法。
仿真实验中新型并行节点下有两个并行任务:锁定目标任务用于识别目标并对其进行定位,跟随移动任务用于控制机器人的速度和方向。其中目标锁定任务采用OpenCV实现机器人视觉中目标的定位,跟随移动任务机器人通过机器人视觉反馈的小球的位置信息将激光雷达扫描与里程计数据,使用AMCL方法进行定位,结合ROS的Move_base进行自主避障跟随。
第六章 结论与展望
本文从经典行为树出发,对行为树进行基础性研究,针对行为树并行执行中的任务同步与资源调度方面存在的不足之处开展研究,课题的创新研究如下:
(1)在行为树并行执行任务同步方面,经典行为树中并行控制节点要求任务节点是相互独立的,然而在实际的应用中并行的任务一般需要相互协作共同完成一项任务。为了解决这个问题,本文将具有层次结构的并行任务引入到行为树的并行任务应用,将并行任务分为领导者任务和跟随者任务。此外,为每个并行任务节点定义执行状态值,区别于经典行为树中的行为树状态,通过各个节点的状态值查看执行的进度,以实现任务间的高效同步,并提出了两种新型的控制节点来优化行为树并行执行任务同步问题。
(2)在行为树并行执行资源调度方面,经典行为树在处理执行任务时的资源调度时,一般采用预设任务优先级,然后根据优先级获取资源的使用权。现有行为树的资源调度研究并未给出具体的实施方法,也没有进行系统的研究。本文结合如今计算机资源调度算法思想,提出四种比较常用的资源调度控制节点,对经典行为树的资源调度进行优化研究,给出了行为树在处理资源调度时一些解决方案。
(3)在行为树并行执行任务同步与资源调度,本文分别针对典型场景进行仿真实验,通过机器人跟随小球的实验案例对强同步与弱同步并行执行算法进行验证,实验结果表明上所提方法有效的优化了行为树的并行任务的同步;通过机器人巡逻案例来对行为树中的资源调度控制机制进行实验验证,实验结果表明所提出的资源控制节点能够达到预期设定结果,满足使用要求。
参考文献(略)