用于可变形两态探测机器人路径规划的环境建模与路径存储方法

本发明涉及机器人路径规划，具体涉及一种用于可变形两态探测机器人路径规划的环境建模与路径存储方法。

机器人路径规划是机器人领域重要研究方向之一。该研究方向有着广泛的应用，例如：核电事故救援、工业喷涂、危险场所物资运输、物流配送、外星球科研探索等等。机器人路径规划主要分为全局路径规划和局部路径规划。全局路径规划需要掌握所有的环境信息，根据环境地图的所有信息进行路径规划；局部路径规划只需要由传感器实时采集环境信息，了解环境地图信息，然后确定出所在地图的位置及其局部的障碍物分布情况，从而选出从当前结点到某一子目标结点的最优路径。从获取障碍物信息是静态或是动态的角度看，全局路径规划属于静态规划(又称离线规划)，局部路径规划属于动态规划(又称在线规划)。

目前，机器人路径规划算法已被广泛研究，但这些算法大都基于固定形态机器人。固定形态机器人在处理复杂环境空间时往往表现不够理想。例如，受机器人已有外形大小限制，无法实现穿越狭窄通道的最优路径规划等等。因此，可变形机器人是一个重要的发展方向。目前，基于可变形机器人路径规划研究仍然较少，属于一个较新领域。

本发明的目的是：提供一种用于可变形两态探测机器人路径规划的环境建模与路径存储方法，适应更为复杂的工作环境，实现移动机器人更多的应用可能。

本发明的技术解决方案是：该用于可变形两态探测机器人路径规划的环境建模与路径存储方法，包括环境建模和基础路径规划，环境建模方面采用一种“二次栅格法”环境建模，基础路径规划工作通过已存在的蟑螂算法完成(见已授权专利ZL2017 10242657.2)；其中，所涉及真实机器人是通过变形技术改变其外观大小的机器人，其能通过变形穿越狭窄区域；其特征是所述环境建模与路径存储方法的步骤如下：

步骤1：基于栅格法完成环境建模

以真实工作空间图片信息为依据，建立一个X行Y列的栅格地图Map，栅格地图左上角被作为原点坐标，生成栅格地图密度为X×Y；其中单元格边长依据机器人原始态与真实工作空间的比例设计；初始状态下，栅格地图中障碍物区域的单元格被标记为“0”，称为“障碍物单元格”；可行区域单元格被标记为“1”，称为“可行单元格”，标记出发点位置S和目标点位置D；将栅格地图中的单元格作为集合元素，则栅格地图描述如下：

上式中，参数(x,y)表示代表单元格坐标；i是单元格下标；参数m 表示单元格是否为障碍物单元格；当ei·m＝1，表示可行单元格；当ei·m＝0，表示障碍物单元格；

步骤2：通过蟑螂算法(见已授权专利ZL2017 1 0242657.2)完成路径规划

得到基于当前栅格密度下的最优路径，由线性表Path记录，Path描述如下：

上式中，ai表示规划好的，机器人将要行走的路径中的单元格；L表示路径长度；s是状态参数，表示机器人状态；ai·s表示ai单元格的s参数；当ai·s＝1，表示机器人处于原始态；当ai·s＝2，表示机器人处于变形态；初始Path中所有元素的ai·s均被赋值为1；

步骤3：路径二次规划

针对步骤2中已规划好的最优路径Path，完成二次规划，依次遍历Path 中所有单元格ai(i＝1，…，L)；

步骤4：路径压缩传输

中央控制端将路径压缩后传送给机器人，压缩方法如下：

pi＝((ai·y-1)×X+ai·x)×10+ai·s

压缩后的路径Path*数据结构为一个线性表，描述为：

Path*＝{pi|i＝1,2,…,L}

步骤5：路径解压缩

机器人得到压缩路径后，执行解压缩，方法为：

上式中mod表示取模运算，div表示取整运算；

步骤6：机器人执行解压缩后的路径

机器人依据路径行进的同时，实现通过ai·s参数完成变形或回复原始态的控制操作。

其中，步骤3路径二次规划执行如下操作：

步骤3.1：扫描单元格ai(x,y)在Map中邻近的三个单元格，e(x,y-1)、e(x-1,y-1)、 e(x-1,y)；如果以上三个单元格均为可行单元格，则变形域Ti构造如下：

步骤3.2：如果变形域Ti已生成，则依据线性表删除操作完成Path调整；判断：如果ai+1(x,y)∈Ti为真，则执行：Path中删除ai+1元素，且L←L －1；

步骤3.3：如果变形域Ti已生成，则修改状态参数：ai·s←2；意味着机器人在此处可变形为状态2。

本发明由于采取以上技术方案，其具有以下优点：

(1)实现了大小可改变的机器人路径规划方案，实现了机器人运用领域更多的可能，机器人处于原始态可以穿越狭窄空间，处于变形态可以探测更大范围。

(2)路径二次规划过程中，构建变形域的同时会减少规划路径种一些不必要的单元格，实现了路径信息的精简。

(3)所提出的可变形两态机器人路径规划方法是基于传统栅格法完成，便于技术人员理解，方法简单且容易实现。

(4)本发明中路径的传输信息是通过技术手段将机器人的状态信息和位置信息压缩为一个单整数，压缩方法简单高效，具体可以节省存储空间2/3，极大缩短了路径传输时间，降低了所需的内存存储空间。

图1是方法执行过程；

图2是栅格法环境建模；

图3是生成的栅格地图；

图4是根据蟑螂算法完成路径规划效果；

图5是路径二次规划效果；

图6是路径二次规划具体执行过程。

下面结合附图和实施例，对本发明的技术方案进行详细地说明，但不应理解为是对技术方案的限制。在下文的描述中，给出了大量具体的细节以便提供对本发明更为彻底的理解。然而，对于本领域技术人员而言，本发明可以无需一个或多个这些细节而得以实施。在其他的例子中，为了避免与本发明发生混淆，对于本领域公知的一些技术特征未进行描述。

如图1所示，给出本路径信息压缩传输方法的执行过程；请参见图1，下面是对方法中各个步骤的详细描述：

步骤S101、基于栅格法完成环境建模：以真实工作空间图片信息为依据，建立一个X行Y列的栅格地图Map，如图2所示：栅格地图左上角被作为原点坐标，生成栅格地图密度为X×Y；其中单元格边长依据机器人原始态与真实工作空间的比例设计；初始状态下，栅格地图中障碍物区域的单元格100被标记为“0”，称为“障碍物单元格”；可行区域单元格200 被标记为“1”称为“可行单元格”；标记出发点300位置S和目标点400 位置D；建模后生成栅格地图如图3所示；将栅格地图中的单元格作为集合元素，则栅格地图描述如下：

上式中，参数(x,y)表示代表单元格坐标；i是单元格下标；参数m 表示单元格是否为障碍物单元格；当ei·m＝1，表示可行单元格；当ei·m＝0，表示障碍物单元格；

步骤S102、使用已有蟑螂算法规划路径：通过已存在蟑螂算法(见已授权专利ZL2017 1 0242657.2)完成路径规划，得到基于当前栅格密度下的最优路径500，如图4所示，由线性表Path记录，Path描述如公式(1) 所示：

公式(1)中，ai表示规划好的，机器人将要行走的路径中的单元格；L表示路径长度；s是状态参数，表示机器人状态；ai·s表示ai单元格的s参数；如图5所示：当ai·s＝1，表示机器人处于原始态600；当ai·s＝2，表示机器人处于变形态700；初始Path中所有元素的ai·s均被赋值为1；

步骤S103、路径二次规划：针步骤2中已规划好的最优路径Path，完成二次规划，依次遍历Path中所有单元格ai(i＝1，…，L)，完成机器人变形参数设置，生成二次规划路径800；

步骤S104、路径压缩传输：中央控制端将路径压缩后传送给机器人，压缩方法如公式(2)所示：

pi＝((ai·y-1)×X+ai·x)×10+ai·s (2)

压缩后的路径Path*数据结构为一个线性表，如公式(3)所示：

Path*＝{pi|i＝1,2,…,L} (3)

步骤S105、路径解压缩：机器人得到压缩路径后，执行解压缩，方法如公式(4)所示：

上式中mod表示取模运算，div表示取整运算；

步骤S106、机器人执行解压缩后的路径：机器人依据路径行进的同时，实现通过ai·s参数完成变形或回复原始态的控制操作。

下面结合图6的流程图，对步骤S103路径二次规划进行详细描述；路径二次规划执行如下具体操作：

步骤S201：设置循环变量i←0；

步骤S202：执行：i←i+1；

步骤S203：构造变形域Ti；扫描单元格ai(x,y)在Map中邻近的三个单元格，e(x,y-1)、e(x-1,y-1)、e(x-1,y)；如果以上三个单元格均为可行单元格，则变形域Ti存在，变形域Ti构造如下：

步骤S204：判断，如果变形域Ti构造成功，执行S205；否则：执行S207；

步骤S205：依据线性表删除操作完成路径Path调整；判断：如果ai+1(x,y)∈Ti为真，则执行：Path中删除ai+1元素，且L←L－1；

步骤S206：修改状态参数：ai·s←2；意味着机器人在此处可变形为状态2；

步骤S207：如果i＜L为真，则执行：跳转至步骤S202；否则执行S208；

步骤S208：输出路径二次规划路径。