路径规划算法主要可分成两种,一种是基于搜索结果的规划,另一类便是本文中将要提及的基于采样的规划。一般而言,基于搜索的规划(如Astar)通常是运行在栅格地图上的。当栅格的分辨率越大时,算法搜索的路径就会越优。

还有一类算法是基于采样的,主要就是RRT和它的变种算法。这类算法的核心在于随机采样,从父节点开始,随机在地图上生成子节点,连接父子节点并进行碰撞检测,若无碰撞,就扩展该子节点。就这样,不断地随机扩展样本点,直到生成一条连接起点和终点的路径。如下图所示,RRT算法的扩展图与盘根错节的树枝十分相似。

这里我们简要讨论两种算法的区别,并配置Python+matplotlib环境来对路径规划算法进行研究。

搜索路径规划算法

这一大类算法,在移动机器人软件上常常是在occupAncy grid的格纹版图上进行计划(只能单纯地理解成二值地图的像素矩阵)以深入择优寻径算法、广度择优寻径算法、Dijkstra(迪杰斯特拉)算法为始祖,以A Star算法(Dijkstra算法上以减小运算量为目的加入了一种启发式代价)则更为常见,如较近期的theta Star算子是在A Star算子的基础上加入了line-of-sight优化所以计划起来的路线不全然依赖于单独的栅格图形如图所示。

 

完备的运算的最大优点就在于其对解的信息捕获能力上是完全的,不过随之形成的最大弊端便是运算复杂性太大。这些缺陷在二维的小尺寸栅格地图上并不突出,但在大尺寸,特别是在多维度规模问题上,如机器臂、蛇形机器人的规划问题将形成很大的计算代价,这也就径直促进了第二大类算法的诞生。

抽样路径规划算法

这些计算通常都是并不直观的在grid地图实现最小栅格分辨率的计划,但是它能够通过在版图上随意撒下特定密度的粒子,来抽象定义为现实版图上的辅助计划。因此,PRM算法及其变种就是从原始版图上开始撒点,并通过抽取roadmap在这样的一种拓扑版图上展开计划;而RRT和其更先进的变体RRT-connect,则是在版图上的每一区域内都能够开始撒点,以迭代生长树的方法,以连结起止点为目的,终于在所连结的版图上实现计划,如图所示。

 

虽然这种基于采样的计算速率比较快,但是所产生的路径损失(可认知为时间)较完备的计算高,而且会出现"有解求不出"的情形(PRM的逢Narrow space卒的情形)。这样的方式,通常会在更高维的城市规划等实际问题上广泛使用。

Python和matplotlib的配置与使用

这里我们使用Anacondda的Python编程环境,使用Visual Studio Code软件进行开发。

Anaconda是专业为了方便于使用Python进行数据挖掘研究而制作的一个应用包,涵盖了在各种数据挖掘研究涉及领域中使用的Python库,而且自带了专业用来处理软件环境中依赖问题的conda包系统。主要优点是实现了外包管理与环境管理的各种功能,而且可以非常容易地处控制多版本Python共存、转换以及各种第三方包使用上的问题。Anaconda使用工具/命令conda来实现对package和environment的控制,其中就曾经包括了python和相应的配套开发工具,如图所示。

 

Anaconda自带人工智能环境,这里我们需要用到的numpy矩阵计算环境、pandas分析环境、matplotlib数据可视化环境等等会自动安装,无需手动配置。

VSCode,全名Visual Studio Code,是由微软公司研发出的一种轻量级程序编写器,免费、开放且能力强劲。它支持了基本上所有主要的程序语言的语法高光度、智能编码补满、自设定热键、括号匹配、编码片段、编码对比Diff、GIT等功能,同时支援插件扩展功能,并根据个人网站发展或者云端使用发展做了调整。该软件跨平台,支持Win、Mac和Linux,启动界面如所示。

 

VS Code编程环境具备项目视图和调试工具,可以让我们更高效的进行代码分析与验证。VS Code会自动检测我们系统当前环境进行加载选择。

这里为了方便后续开发,我将数据可视化部分写成类库的模式,在后续算法验证当中,仅需输入数据调用即可,类库程序如图所示。

 

图表可视化部分是Plotting类,主要作用就是添加坐标点进行显示。这里以queue队列的数据形式进行存储,如图所示。

 

路线规划算法的基本概念为:移动机器人在有障碍物的周围环境中根据相应的评价准则,寻求一个由初始状态至达到目标状态之间的无碰路线。路径规划算法的还有一个划分的方式,即可分为全局路径规划和局部路径规划。

全局路径规划是基于环境全局的信息,这包含了机器人在当前状况下检测不到的所有信号。全局规划把环境信息存放到一幅图中,并利用这张图寻找可能的路线。由于全局算法通常要求花费大量的运算时间,因此不适合于高速多变的动态环境,并且由于全局路径规划必须要预先掌握全局的环境信息,也不适合于未知环境下的规划任务。

局部路径计算系统只考虑了机器人的瞬时环境信号,使得计算数量减少,效率明显提高。但局部路径规划算法,有时并不一定可以让机器人直接抵达目的地点,从而导致了计算全局不收敛。

对移动机器人来说,兼顾非完全微分约束的路径规划问题是该领域的难点所在。非完整微分约束影响了机器人系统的运动速度并且约束也无法去积分,因此无法把这些束缚转换为简化的几何束缚。根据随机采集的路径规划方法,尤其是快速随机搜索树方法,可以将各种约束集成在算法本身之中,因此可以很有效的解决有非完整微分约束的路径规划问题。

在深入研究自己自主规划课题之前,应先形成相对比较完善的自主规划系统,然后再以这个系统为指导,对自己自主规划的各种具体课题加以研究。本节拟针对独立人工智能机器人的思考方法、行动方式、任务行动等特征,形成与之相适应的自主性体育运动规划系统。并根据人工智能机器人的数量种类和规模,把自主性运动计划细分成单一人工智能机器人的运动计划和多人工智能机器人协同的运动计划二种规划系统。

文章重点涉及了以下几个常见的运动规划算法:图搜索法、RRT算法、人工势场法、BUG算法等,并对部分方法的自身问题也进行了一些改进研究。

此次设计方案以算法的验证为主,通过查阅相关文献,根据相关文献资料确定此次设计实验的算法,推导算法的实现过程,最终通过代码进行实现数据可视化分析来完成本文的工作,如图所示。

 

此次设计先对图搜索算法、RRT及RTT改进算法、BUG算法、人工势场法进行理论的分析和阐述,通过Python编程+ Matplotlib数据可视化的方式来对路径搜索算法进行可视化的展示和分析。

这个研究工作主要是指通过对ROS机器人系统所进行的仿真实验,而ROS技术(Robot Operating System,下文简写"ROS")则是指一个广泛应用在人工智能方面开放的多元操作系统。它提供了控制系统所需要的全部特性,如硬件抽象性,系统底层的控制,对常用功能的应用,进程的数据传递,和包处理等。它还具有用来检索、翻译、汇编、和跨计算机执行代码所必需的工具和库函数的功能。

在ROS系统下可以通过Gazebo物理仿真+Rviz三维数据可视化的方式对算法进行分析。在ROS中实现自己的路径规划算法需要以plugin的方式,并且继承nav_core::BaseGlobalPlanner接口,实现效果如图所示。

仿真测试部分在Gazebo环境下搭建机器人模型,通过仿真系统将激光雷达数据、里程计数据、姿态数据进行模拟,传感器数据传递到navigation导航框架当中实现路径规划及自主导航功能。