题目：基于进化计算的多机器人路径规划

随着智能机器人技术的发展，多机器人系统在空间探测、灾难救援、工业生产等领域发挥着越来越重要的作用。目前多机器人技术研究的范围和深度都不断得到拓展，而路径规划在提高机器人工作效率、保证机器人安全等方面发挥着十分重要的作用。本文针对多机器人在复杂环境下执行特定任务的技术需求，以进化计算为工具，从单机器人路径规划问题入手，着重研究了多机器人的路径规划问题，在多机器人路径规划的实现算法和实验验证等方面取得了具有应用参考价值的结果，主要研究内容包括：（1）基于多障碍物环境建模的多机器人路径规划。在环境建模时，使用多边形来覆盖障碍物，并基于多边形的顶点进行编码；通过加入一个过滤操作，缩减了可行解的搜索空间，大大提高了算法寻找最优解的速度，节省了路径规划的时间。（2）已知环境下面向复杂任务的多机器人路径规划。研究多个单任务机器人完成多个单机器人任务的问题，首先将此问题建模为二分图最优匹配问题，利用匈牙利算法和Kuhn-Munkres算法实现任务的最优分配，然后根据各机器人分配到的任务，为其进行路径规划。（3）复杂环境下的单机器人路径规划。采用遗传算法和滚动窗口虚拟子目标结合的方法，首先对部分已知的环境信息进行建模，规划出一条最短路径，并将路径所经过的障碍物端点设为全局子目标点；其次，当机器人由一个全局子目标移向下一个全局子目标时，通过传感设备对局部信息进行探测，并确定局部虚拟子目标，实现局部路径规划。（4）复杂环境下的多机器人路径规划。首先根据部分已知信息，为每个机器人规划一条最短路径；各机器人行驶时，将新探测到的环境信息与其它机器人共享，构建局部地图；各机器人根据局部地图，规划局部路径；当机器人之间路径发生冲突时，按照冲突消解机制，解决冲突。最后采用AS-R机器人、计算机、摄像机、无线网络等搭建了多机器人路径规划实验平台。通过实验证明了本文所提的算法的有效性和可行性。