狭隘环境下一种多机器人路径规划方法

狭隘环境下多机器人路径规划使用共享资源时，极易产生冲突，优先顺序化是解决共享资源冲突的一个重要技术。本文提出了一种基于学习分类器的动态分配优先权的方法，提高机器人团队的性能。首先机器人通过XCS优化各自的行为，然后引入和训练高水平的机器人管理者来分配优先权解决冲突。本方法适用于部分可知的Markov环境，仿真实验结果表明本文所提方法用于解决多机器人的路径规划冲突是有效的，提高了多机器人系统解决路径规划冲突的能力。

近年来，多机器人路径规划已成为机器人领域中的一个热点问题。根据机器人对环境的了解程度， 可以分为两种类型：环境信息完全已知的全局规划和环境信息完全未知或部分未知的局部路径规划[1] [2]。

多机器人路径规划是为均处在同一个简单或复杂，静态或动态，已知或未知的工作空间中的每个机器人找到一条路径，能避开障碍物并能保证机器人之间无碰撞，最后以最小或较小的消耗完成自己的任务[3] [4]。由于多个机器人间存在资源竞争、且共处一个工作空间，这就造成了机器人间的冲突，解决机器人间的冲突已成为多机器人系统要解决的关键问题。

解决路径规划冲突问题，已有众多学者使用众多方法做了多年的深入研究并产生了大量研究成果[5]-[7]。

已有的研究解决方法大致可以分为集中式和离散式两类。

集中式方法是将所有的机器人当作一个整体进行路径优化， 但在不同的环境下优化结果不可靠， 特别是对于部分可知的MDP 环境或者机器人太多的环境。离散式方法是分别对单个的机器人进行路径优化，并随时解决优化过程中出现的冲突。两种方法共同的缺陷是算法的计算时间太长，仅能用于较小的环境，且不能保证在较短的时间内总是获得优化或接近优化的结果。

基于上述分析，本文提出采用基于XCS 的离散启发式方法用于机器人的路径规划，机器人的优先权由其XCS 的预测回报值来确定，而由集中式高水平的规划机器人动态分配各机器人的优先顺序，以解决机器人间的冲突，共同完成多机器人系统的路径规划。

2. 相关技术原理 2.1. Q 学习 Q 学习是由Watkins 1989 年提出的基于Markov 环境的一种学习算法(MDP) [8]。其原理是通过对感知的环境状态采取各种试探动作，获得此种试探动作对此种环境状态的奖励或者惩罚信号，并能不断调整学习策略以获得较大的奖励或较小的惩罚，同时反馈给其它机器人，并能够保证学习的收敛性。

单机器人的学习环境是基于Markov 提出的有限四元组, , , S A f ρ<> ， 其中S 是有限环境状态集，A为机器人有限动作集， []:0,1fSA S××→为状态转换概率函数。

:, 1, , i SA SR inρ××→=为机器人的回报函数。

多机器人的学习环境是基于MR-MDP， 是一个随机的四元组, , , S A f ρ<> 。

S 为离散的环境状态集、A 为作用于机器人的动作集， 1nAAA=××，n 为机器人数量。

[]:0,1fSA S××→为状态转换概率函数。

:, 1, , i SA SR inρ××→=为机器人的回报函数。在多机器人系统，状态转换是所有机器人联合行