多机器人定位与任务分配技术解析

### 多机器人定位与任务分配技术解析 #### 1. 移动机器人 UKF 定位方法 在移动机器人领域，定位是一项关键技术。一种基于无迹卡尔曼滤波器（UKF）的定位框架被提出，该框架使用 2D 激光测距仪。通过基于局部切线值方差的分割算法，能够为移动机器人定位提供线段、角点和曲线段等特征。从这些特征中提取的地标不仅具有参数特征，还包含不确定性信息。 系统利用观测到的几何地标与先验地标位置地图之间的匹配，通过 UKF 为移动机器人提供最优的位姿估计。实验结果表明，该方法在室内环境中具有较高的准确性和鲁棒性。 从图 3 可以看到 UKF 定位方法的位姿估计误差，分别在坐标 (x, y) 和方向 θ 上，同时还叠加了估计的 1σ 置信区间。可以发现，误差并没有发散，说明该方法具有较好的稳定性。 图 4 展示了定位实验的结果，其中蓝色线表示里程计预测的轨迹，红色线是估计的轨迹，黑色线是真实数据。随着时间的增加，里程计预测的轨迹逐渐偏离真实路径，而 UKF 能够较为准确地跟踪机器人的位置，即使轨迹包含急转弯。这表明机器人可以通过融合传感器信息进行自我定位，从而实现成功导航，证明了基于 UKF 的定位算法的有效性。 #### 2. 多机器人动态任务分配问题 多机器人系统在行星探索、海底勘测、排雷、地图绘制、救援等领域有着广泛的应用。在这些应用中，多机器人任务分配（MRTA）是一个关键问题。现有的多机器人任务分配研究存在一定的局限性，大多数算法没有考虑到多机器人系统的动态性和环境中的障碍物。 本文提出了一种动态任务分配算法，用于解决多个机器人访问多个目标的问题。该算法专门针对机器人具有不同起始和结束位置的环境进行设计，同时考虑了平衡每个机器人访问目标数量的约束条件。 ##### 2.1 整数线性规划模型 多机器人任务分配问题可以表述为：给定 n 个随机分布在某一区域的目标，以及 m 个通常位于该区域外且具有不同起始和结束位置的机器人。m 个机器人必须访问这 n 个目标，且每个目标只能被一个机器人访问一次。为了节省能源和时间，需要最小化访问所有目标的总距离。同时，由于工作量平衡的要求，每个机器人访问的目标数量应该尽量平均。 基于上述问题，提出了以下整数线性规划模型： - 距离目标函数： \[ f(x)=\sum_{i = 1}^{m}\left(d\left(S_{i},T_{i1}\right)+\sum_{k = 1}^{n_{i}-1}d\left(T_{ik},T_{i(k + 1)}\right)+d\left(T_{in_{i}},E_{i}\right)\right) \] 其中，$T_{ik}$ 是机器人 i 访问的第 k 个目标，$d\left(T_{ik},T_{i(k + 1)}\right)$ 是 $T_{ik}$ 和 $T_{i(k + 1)}$ 之间的距离，$S_{i}$ 是机器人 i 的起始仓库，$E_{i}$ 是机器人 i 的结束仓库，$n_{i}$ 是分配给机器人 i 的目标数量。 - 任务数量约束： \[ g(x)=\max\left(n_{i}\right)-\min\left(n_{i}\right)\in\{0,1\} \] - 约束任务分配问题的表述为： \[ \min f(x) \] \[ \text{subject to } g(x) \] ##### 2.2 多机器人系统的群体架构 本文讨论的多机器人系统采用分层群体架构。在该架构中，采用了领导者 - 追随者的组织结构。领导者机器人负责监督整个系统，以增强全局协调能力，并在一个或多个机器人部分或完全故障的情况下支持自组织能力。同时，每个机器人都是一个自主代理，在物理上是分布式的，能够自主执行个体任务，并在必要时与其他机器人进行通信。 领导者机器人可以通过任何有效的策略动态选择。本文提出了一种基于索引的方法，根据每个机器人预定义的唯一索引进行选择。当索引为 $i\in\{1,2,\cdots,m\}$ 的前领导者机器人损坏并失效时，索引为 $i + 1$（如果 $i<m$）的机器人将被选为新的领导者。 #### 3. 改进的蚁群系统（MACS） 为了解决多机器人任务分配问题，提出了一种改进的蚁群系统（MACS）算法，该算法是在经典蚁群系统（ACS）的基础上进行改进的。 ##### 3.1 初始化 由于固定目的地多仓库多旅行商问题（MTSP）的特点，MACS 算法在初始化阶段与经典 ACS 有所不同。需要考虑机器人的不同起始和结束仓库。在 ACS 中，所有蚂蚁随机放置在目标上，而在 MACS 中，所有蚂蚁随机放置在机器人的起始仓库或结束仓库上，即随机放置在 $S_{i}$ 或 $E_{i}$（$i = 1,2,\cdots,m$）上。所有蚂蚁将从一个仓库开始，在相同的空间中进行搜索。 同时，蚁群的信息素矩阵和成本矩阵的初始化也进行了修改。需要计算并存储从一个仓库到所有目标的信息素和成本。 ##### 3.2 解决方案构建 在解决方案构建阶段，MACS 算法进行了以下三个方面的修改： 1. **任务数量分配阶段**：该阶段用于实现任务数量约束。任务数量等于每个机器人分配到的目标数量。如果目标数量 n 能被机器人数量 m 整除，则每个机器人的任务数量 $n_{i}$ 应为 $n/m$；否则，设 s 为商，r 为余数，则 $n_{i}$ 可以定义为： \[ n_{i}=\begin{cases} s + 1, & \text{if } (r>0 \text{ and } u<u_{0}) \text{ or } (r>0 \text{ and } v<r)\\ s, & \text{otherwise} \end{cases} \] 其中，u 是一个随机均匀变量 [0, 1]，$u_{0}$ 是一个影响不同机器人目标数量的参数，v 表示目标数量为 $s + 1$ 的机器人总数，w 表示目标数量为 s 的机器人总数。经过这个阶段，每个机器人的任务数量就确定了，并且满足 $\sum_{i = 1}^{m}n_{i}=n$。 2. **路径构建**：每个蚂蚁从初始位置开始，选择未访问的目标来构建路径。在 MACS 中，解决方案构建过程比 ACS 稍微复杂一些。假设一只蚂蚁从 $S_{p}$ 开始，如果它已经访问的目标数量等于 $n_{p}$，则蚂蚁返回 $E_{p}$。然后，蚂蚁选择一个未访问的起始仓库 $S_{i}$，从该仓库出发并迭代选择未访问的目标。蚂蚁访问过的目标记录在其禁忌表中，直到所有目标、起始仓库和结束仓库都被访问，蚂蚁才构建出一个有效的解决方案。定义蚂蚁数量为 a，则有 a 个解决方案由 a 只蚂蚁构建。 每只蚂蚁独立选择下一个城市，从目标 i 移动到目标 j 的规则可以表示为： \[ j=\begin{cases} \arg\max_{l\in N_{i}^{k}}\left[\tau_{il}^{\alpha}\eta_{il}^{\beta}\right], & \text{if } q\leq q_{0}\\ \text{random selection}, & \text{otherwise} \end{cases} \] 如果 q 大于 $q_{0}$，蚂蚁 k 从目标 i 移动到目标 j 的概率可以表示为： \[ p_{ij}^{k}=\