地面移动机器人运动规划与运动协调的若干算法研究

论文摘要

运动规划和协调是自主移动机器人和多机器人系统研究中的部分基础和关键问题。由于实际应用中机器人的通讯和感知范围有限,环境信息未知或不完整,因此本文的主要内容为在有限通讯和感知条件下,在未知或不完整环境信息中,研究地面移动机器人的运动规划以及多机器人系统的运动协调中的一些问题,建立从个体的运动规划能力到群体的协调运动能力的一个整体框架。本文从运动规划和协调角度,针对室内环境,在以下三个方面开展工作:（1）覆盖规划是环境建模的基本问题之一。设计合理的运动策略,尽量完整地覆盖未知环境是探索未知环境的一个重要内容。（2）在不完整信息情况下,需要一个能够快速重规划的算法,该算法要能够结合环境模型的特点,根据环境的变化增量重规划。（3）在个体机器人运动规划的基础上,研究多机器人系统如何协调一致地运动。文中的主要研究工作和贡献如下:（1）未知环境的覆盖规划中,采用改进的滑动算法,并结合环航和随机行走等策略,使得多机器人队伍能够一边探索障碍物信息,一边增量的构建构型空间。这样不仅完成了障碍物边界信息的探测,同时得到与机器人形体无关的状态空间。相比于传统滑动算法,增量算法使得构型空间可以从局部逐渐构建,并且可用于多机器人系统,大大提高了效率。（2）设计了一种改进的基于近似Voronoi图的GVD（Generalized Voronoi Digram）算法。该GVD算法基于VDC（Van Der Corput）采样序列,在产生GVD时,使用VDC序列控制精度更加方便,与简单采样相比计算性能也得到了改善,并且还具有优良的均匀性。（3）为了克服简单重规划的低效率,设计了一个在几何环境下运行的动态A*算法-GD*Lite。该算法以一个探测临界点的Morse函数为基础,结合D*Lite可以快速的在信息不完整的几何环境中重规划。（4）根据市场方法原理,建立了一个集市型市场结构,用于多机器人的任务或资源分配。机器人之间可以直接采用最高价开叫拍卖方式磋商,拍卖出现矛盾时,其它可选资源的潜在利润可以供其继续出价。（5）设计了一个基于对策论的局部运动协调方法。通过适当的形式化,将运动协调问题转化为机器人在通讯辅助下,局部性的和周围的机器人对策的过程,并且采用了GD*Lite扩展节点的思想。这些措施使得在传统对策论框架下多个机器人能快速的协调运动。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 引言
• 1.2 地面移动机器人及多机器人研究概况
• 1.2.1 国外概况
• 1.2.2 国内概况
• 1.3 地面移动机器人运动规划概述
• 1.3.1 移动机器人运动规划的形式化描述
• 1.3.2 移动机器人运动规划的环境模型
• 1.3.3 运动规划算法介绍
• 1.4 多机器人系统运动协调概述
• 1.4.1 多机器人系统简介
• 1.4.2 多机器人系统的典型开放问题
• 1.4.3 多机器人系统的主要研究内容
• 1.4.4 多机器人系统的运动协调
• 1.5 研究路线
• 1.6 本文成果
• 1.6.1 主要工作
• 1.6.2 创新点
• 1.7 小结
• 2 未知环境边界覆盖与构型空间的建立
• 2.1 引言
• 2.2 同时覆盖边界并建立构型空间
• 2.2.1 构型空间定义
• 2.2.2 构型空间障碍
• 2.3 未知环境构型空间的建立
• 2.3.1 形式化定义
• 2.3.2 滑动算法
• obs'>2.3.3 多机器人构建C_obs
• 2.3.3.1 环航探索算法
• 2.3.3.2 增量计算C-space
• 2.3.4 实验与结果
• 2.4 一个完备的边界覆盖算法
• 2.4.1 算法基本描述
• 2.4.2 基于可见性的单元分解与边界覆盖
• 2.4.3 多机器人边界覆盖
• 2.4.4 实验与结果
• 2.5 小结
• 3 拓扑地图的建立
• 3.1 引言
• 3.2 基于自由空间分解的方法
• 3.2.1 有孔多边形分解问题
• 3.2.2 算法思想
• 3.2.3 有序下单调链对的产生
• 3.2.4 划分为单调多边形
• 3.2.5 单调多边形的凸划分
• 3.2.6 算法时间复杂性
• 3.2.7 实验与分析
• 3.3 基于Voronoi图的方法
• 3.3.1 Voronoi图与机器人学
• 3.3.2 GVD的构建
• 3.3.3 采样序列
• 3.3.4 基于VDC序列的GVD
• 3.3.5 实验与分析
• 3.4 可旋转时的拓扑图
• 3.5 小结
• 4 不完整环境信息下的运动规划
• 4.1 引言
• 4.2 用Morse函数检测拓扑地图的变化
• 4.2.1 Morse检测函数的定义
• 4.2.2 临界点的计算
• 4.2.3 自由空间连通性的变化
• 4.2.4 非光滑边界的一般情况
• 4.3 几何环境中的动态A*算法
• 4.3.1 D*Lite规划
• 4.3.2 几何环境中的D*Lite
• 4.4 实验与分析
• 4.5 小结
• 5 基于经济学相关理论的协调方法
• 5.1 引言
• 5.2 市场机制与应用
• 5.2.1 决定代价与收入
• 5.2.2 出价过程
• 5.2.3 集市型市场结构
• 5.2.4 多机器人编队初始化中的位置分配
• 5.3 基于对策论的协调
• 5.3.1 对策论模型
• 5.3.2 形式化运动协调问题
• 5.3.3 局部的不合作n人对策
• 5.3.4 实验与分析
• 5.4 小结
• 结束语
• 致谢
• 附录
• 参考文献