- 文献综述
多机器人追逃问题是对自然界中生物群体活动的模拟，来源于自然界的动物捕食研究如何指导一群自主移动机器人分别充当追捕者和被追捕者。是分布式系统中多智能体合作与协调的问题，在实际中，这是一个集成混合系统理论、导航、计算机视觉、通讯等学科的分布式系统。虽然我国这一方面起步较晚，但由于国家对自动化领域和智能机器人的重视，大力支持研究工作，我国的单机器人技术和理论水平已和国际领先水平相当，但在实际应用等方面，仍有欠缺。而在多机器人方面的研究，由于多方面的限制，还有待更进一步。
从翻阅的文献资料来看，理论、实际研究界主要有以下方案：
早期的追逃问题开始于20世纪80年代，国外便开始研究。目前的Benda[1]首先提出了单猎物追捕问题，即在固定环境中，多机器人协作共同追捕单逃跑者的栅格模型，机器人只能在水平或垂直方向运动，四个追捕者需要同时占据被追捕者所在栅格的四个可运动方向上的栅格，才能算是成功追捕，这种直角对策模型只是一种粗略的离散化方案，Korf[2]在此基础上增加了对角线方向运动，首次将多机器人的追逃问题考虑为动态下的博弈问题。然而，在这个方案中，追捕者和逃跑者只能依次轮流选择运动方向，并不符合现实生活中的实际运动情况。为使得追逃双方能够自动生成并不断学习进化控制策略，Haynes[3]提出了使用强类型遗传规划算法（STGP:Strong Type Genetic Programming），最终使控制策略稳定收敛，但在这种算法下，控制策略需要通过学习获得，各个追捕者没有合作，只能用贪心算法去控制追捕者，预期的协同行为并没有得到实现，所以，最终，连最简单的沿直线逃跑的逃跑者也能从各追捕者手中成功逃跑。F.Ho[4]则采取复杂性更低的概率爬山法方案，在这种方案中，逃跑者的能力低于追捕者，速度仅仅是追捕者速度的90%，尽管追捕者最终成功捕获目标，但个人认为。并没有实际的研究价值。Yamaguchi[5]运用包含反馈的控制率去研究针对静止目标的机器人不对自适应的队形控制，采用矢量控制，使得追捕者可在发现目标后依靠自动导航，通过合作将目标包围并最终抓捕成功。LaValle[6]和Simov[7]提出在已知的多边形环境[8]中和简单连接的二环境[9]中，将追逃问题抽象为有限图算法问题，并且基于这样的一种原则：如果逃跑者处于某个追捕者的视线上时，便被认为成功捕获。Kyle、Klein[10]等人研究的是在有障碍物的环境中基于视线的追逃问题，在保证追捕者和逃跑者速度、视野能力完全相同的情况下，研究保证追不成功的所需要的追捕者的数量和环境多边形的边数与障碍物数量之间的关系。Deepak和Bhadauria[11]等人证明了在追逃过程中，如果假设每个机器人的速度能力相同并且都具有实时获取其他机器人位置的能力条件下，仅需要三个追捕者就可以成功捕获一个逃跑者。Hespanha[12]详细描述了部分马尔科夫信息博弈，是在不完全精确的地图上的追捕问题，将围捕和探索地图相结合，提出了后退水平控制策略。Subhash和Suri[13]等人则模仿动物世界中的群狼围捕单个狮子，研究了K个追捕者成功追捕一个逃跑者问题，得出了以下结论：如果某个时刻逃跑者位于追捕者团队的 k-凸包内，则一定能够实现有限时间内成功捕获。此外，他们还针对欧式空间的紧致且凸的子空间中发生的追捕问题给出了一个简单的抓捕策略能使追捕者成功抓捕逃跑者。
以上的追捕-逃跑问题的研究都是基于各机器人对环境已知的条件下。而当环境未知时，一般需要将其转化为已知环境下的追捕-逃跑问题。通常采取的方法是在追捕之前通过学习来生成多机器人合作地图。美国海、空军部和加州大学伯克利分校的Sastry小组[14]研究了未知环境下用无人机(UAVs: Unmanned Aerial Vehicles)和地面无人车辆(UGVs: Unmanned Ground Vehicles)组成的追捕团队合作追捕地面逃跑机器人。其中无人机和无人车辆装备的传感器系统都是不精确的，manned Ground Vehicles)组成的追捕团队合作追捕地面逃跑智能体的概率模型。将地图探索和追捕目标合并为一个问题。在仅仅知道关于环境的不精确的先验地图的情况下，考虑了传感器获取信息的不确定性，重点研究追捕者在追捕的同时合作建立环境模型。以建立较精确的环境模型。他们考虑了局部最优和全局最优两个计算可行的贪心追捕策略，通过仿真结果来比较这两个策略，证明了全局最大策略下以下因素影响着期望捕捉时间：追捕机器人的感知能力、速度以及追捕场地大小，并且对该时间的有限性进行了证明。此外针对机器人用不精确传感器搜索环境的追捕-逃跑问题[15]，他们也进行了研究并提出四种搜索策略：全局最优、局部最优、无重复的全局最优和无重复的局部最优，并进行了比较。
我国对多机器人追捕问题的研究工作起步较晚，八十年代末国家“八六三”计划自动化领域智能机器人主题和国防科工委才陆续立项投资支持机器人的研究工作。目前单机器人的总体技术水平与性能已经接近或部分超越国际领先水平，但在研究规模、投资强度、技术水平、成果应用与效益等方面都大大落后于发达国家。而在多机器人方面由于经费和实验环境的限定，进行的相关研究很少。王月海[16]对已知环境下多机器人追捕问题进行了研究，考虑了在同等条件，追捕智能体、逃跑智能体具有相同的视野、速度和运动机会下机器人团队对单猎物和多猎物的合作追捕问题，实现了追捕团队Pareto 最优追捕决策机制，提出了一种可求出机器人合作追捕单猎物和多猎物Pareto 最优策略的算法，并利用博弈论中的均衡理论研究多个理性智能体组成的多智能体系统的最优合作问题。苏治宝[17]提出了一种在连续未知环境中实现多移动机器人协作围捕单个移动目标的整体方案，通过Q-学习算法对追捕智能体的各种行为进行选择实现对移动目标的围捕。Cao为了实现在未知环境下多移动机器人的围捕，将围捕任务建模为排队、随机搜索、包围、捕捉和预测五种状态提出了排队、搜索、包抄、捕捉、预测和方向优化策略，结合状态转换条件保证了任务的顺利实现，同时，赋予逃跑智能体一种安全运动策略，增加了围捕的难度。 洪炳熔[18]等人提出了基于博弈框架下完全且完美信息的多追 捕者-单逃跑者的追捕模型，他们将多机器人的追逃问题等价为两个局中人的离散动态对策问题。通过构造威胁评估函数并求解追捕者的支付矩阵来得到每次走步时的追逃双方的最佳策略。不过将追逃双方的博弈考虑为完全完美信息的博弈不符合实际当中的情况。此外，他们还针对二维连续的环境中追捕者速度小于逃跑者速度的情况下实现成功捕获的约束条件进行了研究并给出了相应约束条件下追捕者和逃跑者的走步策略[19]。在追捕联盟的生成方面，方宝富[20]等人首先证明机器人追逃问题中的联盟收益具有独立性，然后提出了基于贪婪最优收益的追捕联盟算法。该算法中追捕联盟中的各子联盟数量是根据逃跑者的数量来决定的。在确定子联盟的个数之后再根据追捕收益对各个子联盟的领导者进行选定，最后利用贪婪最优算法将新成员扩展到各个子联盟里面直到所有的追捕者都属于且只属于一个联盟。李珺[21]等人认为追捕问题和多机器人的路径规划问题类似，因此可在对逃跑者位置进行精确预测的情况下，求解出地图中追捕机器人将逃跑机器人成功捕获的最佳路径，他们将未知环境下的多追捕机器人合作抓捕多个逃跑机器人的追捕过程分为三个步骤：首先创建环境地图，然后生成追捕团队，最后团队成员合作将目标捕获。付勇[22]等人则设计了一种伏击方案，将逃跑者驱赶至追捕者认为最佳的围捕区后再采用合适的围捕策略抓捕逃跑者。此外，他们还证明了当追捕者与逃跑者的速度的比值大于某一值时，就能保证将逃跑者捕获。曹志强[23]将未知环境中的围捕任务建模为五种状态，通过将状态优化和状态转换条件相结合，确保追捕者将逃跑者顺利抓获。同时为了增加追捕者围捕成功的难度，逃跑者还被赋予了一种比较智能的逃跑策略。
但以上研究都是针对追捕者的能力不低于逃跑者，而如果当追捕者能力低于逃跑者时的相关研究还有待深入和加强。在长期研究过程中，大多数研究都是在逃跑者比任何追捕者都要慢的前提下来确保追捕成功。但在现实世界总，逃跑者的逃跑速度至少应该和追捕者一样快。与慢速逃避者的大量研究工作相比，很少有人研究过快速逃避者。 Pachter 处理一个逃避者和一个较慢的追求者问题;它指出，即使逃避者快速运行，在某些初始状态下，并且给定半径为lgt; 0的捕获圆和由墙限制的限制区域，仍然可以保证捕获。蔡等人提出了一种具有优越逃避者的多玩家追捕逃避差异游戏的方法。他们的论文主要关注追捕者的策略，而逃避者的策略没有明确解决。此外，对于快速逃避者，虽然可以保持追击者围绕逃避者的形成不变，即围绕逃避者的分布角度，但是不可能将追捕者的质心保持在逃避者的位置。 这可能导致追求不成功。王等人通过关注追捕者的策略，使用追踪者的形成控制来捕捉优秀的逃避者，同时假设逃避者以预定义的简单策略运行。然而，从双方的角度来看，应该考虑对PE比赛进行全面分析。在某些初始条件下，成追捕快速逃避者是可能的。
机器人追逃问题中，机器人的追捕性能受到机器人数量影响，基本规律是，追捕者数目越多，越容易成功追捕，进一步来说，则需要对追捕者和逃跑者的速率比值做出研究。这也是我着手的重点，从追捕者的数量、速度上进行不同的配置，分别研究他们在几种经典的追捕策略下的追捕效果。
参考文献
以上是毕业论文文献综述，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
