一种基于布尔约束的机器人最优路径规划方法

摘要

一种基于布尔约束的机器人最优路径规划方法，首先对机器人全局环境进行划分，并写出空间集合及其邻接矩阵；然后输入机器人的布尔约束任务要求，根据任务要求更新邻接矩阵；再计算任务间的最短距离和对应的路径并储存；随机产生一个满足布尔约束任务要求的初始任务序列，并计算它的最短移动距离及其对应的路径；再对初始任务序列进行模拟退火算法优化；最后输出最优任务序列、最短移动距离及其对应的路径；本发明使机器人在满足任务要求的前提下移动距离最短，较大程度的降低机器人移动成本和时间成本，提高效率，具有良好的应用前景。

说明书

技术领域

本发明涉及机器人技术领域，具体涉及一种基于布尔约束的机器人最优路径规划方法。

技术背景

随着科技的进步和社会的发展，移动机器人的应用越来越广泛，涉及军事、工业、农业、家庭等领域。在机器人路径规划研究领域中的三大核心问题是机器人的定位、任务的分配和路径规划技术，其中，路径规划是移动机器人避开障碍物到达任务目标、完成任务内容的首要条件。例如：家庭服务型清洁机器人需要对室内环境进行合理的路径规划以完成清洁任务；农业采摘机器人需要路径规划才能在农作物间穿行以完成采摘任务；工业机器人也需要进行路径规划才能在共享工作空间中完成给定的任务。

机器人在家庭服务、农业助力、工业环境、军事救助等方面都得到广泛的应用。在这些应用中，机器人路径规划尤为重要，机器人路径最优规划是指：在其工作环境中找到一条从起始状态到目标状态的能完成任务要求并避开所有障碍物的路径，且移动路径最短。

经过多年的研究，对于一般任务要求的最优路径规划方法已经比较成熟，然而，随着任务的复杂度越来越高，如具有布尔约束的任务要求(布尔约束主要包括与、或、非三种描述，具有布尔约束的任务要求是指机器人从起始状态到目标状态的路径满足必须经过某些点完成任务、从某些点中选择部分完成任务、必须避开某些点)的机器人最优路径规划，一般任务要求的最优路径规划方法已经无法满足实际需求。

发明内容

为了克服上述现有技术的缺点，本发明的目的是提出一种基于布尔约束的机器人最优路径规划方法，使机器人在满足任务要求的前提下移动距离最短，较大程度的降低机器人移动成本和时间成本，提高效率，具有良好的应用前景。

为了达到上述目的，本发明采用如下技术方案：

一种基于布尔约束的机器人最优路径规划方法，包括以下步骤：

步骤一：对机器人全局环境进行划分，并写出空间集合及其邻接矩阵；

步骤二：输入机器人的布尔约束任务要求；

步骤三：根据任务要求更新邻接矩阵；

步骤四：计算任务间的最短距离和对应的路径并储存；

步骤五：随机产生一个满足布尔约束任务要求的初始任务序列，并计算它的最短移动距离及其对应的路径；

步骤六：对初始任务序列进行模拟退火算法优化；

步骤七：输出最优任务序列、最短移动距离及其对应的路径。

所述的步骤一具体为：

将全局环境划分为m个空间，分别用集合R＝{R

邻接矩阵W为一个m×m的对称矩阵，如果空间R

所述的步骤二具体为：

将任务分为五类：

第一类：起点任务，用集合T

第二类：终点任务，用集合T

第三类：布尔约束“与”任务，用集合

第四类：布尔约束“或”任务，分别用集合

第五类：布尔约束“非”任务，用集合

那么将所有任务用布尔约束描述为：

所述的步骤三具体为：

将邻接矩阵中所有布尔约束“非”任务所在行和列均设置为∞，即：

所述的步骤四具体为：

根据邻接矩阵W利用Dijkstra算法计算两个空间之间的最短移动距离和对应的路径，计算从源点R

1)创建两个集合S、U和一个1×m的全0矩阵P，其中S是已经找到最短路径的顶点，U是还待计算的顶点，令S＝R

2)将集合U中具有最小距离的顶点R

3)更新集合U中顶点的距离，若从源点R

4)若目标点R

5)根据矩阵P通过回溯法求解路径l

利用上述的Dijkstra算法分别计算集合T

所述的步骤五具体为：

根据布尔约束的任务要求，选择所有“与”任务并在每个“或”任务中选择一个任务组成中途任务序列，即：

最优任务序列：M

最优任务序列的最短移动距离：D

最优任务序列的最短移动距离对应的路径：L

所述的步骤六具体为：

对初始任务序列进行模拟退火操作，从初始温度

第一种操作，两点交换操作：

在任务序列

第二种操作，倒序操作：

在任务序列

第三种操作，重插入操作：

在“或”任务中随机选择一个任务集合

在得到新的任务序列M

如果新的任务序列M

另外，如新的任务序列M

M

如果新的任务序列M

M＝M

所述的步骤七具体为：

当温度降低到终止温度

本发明的有益效果为：

对于给定的全局环境和基于布尔约束的任务要求，任务选择的组合和任务序列的排列具有多种可能性，对于不同的任务选择和任务排序，机器人对应的移动距离可能存在很大的差异，因此从布尔约束的任务中如何选择任务，对任务如何进行排序，各个任务点之间如何选择避开所有障碍物的最优路径时十分有必要的。本发明利用Dijkstra算法结合模拟退火算法的智能算法，首先将所有可能关联任务点之间的最短移动距离和对应的路径通过Dijkstra算法进行求解并储存，随机选择满足布尔约束的任务产生初始任务序列并对初始任务序列进行模拟退火操作，最终找到最优的任务序列、最短移动距离及其对应的路径；本发明不仅具有良好的通用性，而且能够快速找到最优的任务序列、最短移动距离及其对应的路径，较大程度的降低了移动成本和时间成本，扩大机器人的应用领域，代替人完成复杂的工作任务，提高生产生活自动化水平，具有良好的应用前景。

本发明具有通用性，不仅能够规划完成满足布尔约束任务要求的最优路径，使得机器人的移动距离之和最短，达到降低移动成本和时耗的目的；还与智能算法结合起来，提高计算的高效性。

附图说明

图1是本发明方法的流程框图。

图2是实施例机器人的全局环境图。

图3是实施例机器人的空间集合图。

图4是步骤五模拟退火操作的流程框图。

图5是实施例机器人的最优路径规划图。

具体实施方式

以下结合实施例和附图对发明作进一步说明。

参照图1，一种基于布尔约束的机器人最优路径规划方法，包括以下步骤：

步骤一：对机器人全局环境进行划分，并写出空间集合及其邻接矩阵；

本实施例机器人全局环境如图2所示，将全局环境划分为28个空间，分别用集合R＝{R

邻接矩阵W为一个28×8的对称矩阵，如果空间R

步骤二：输入机器人的布尔约束任务要求；将任务主要分为五类如图3所示，本实施例中的五类任务如下：

第一类：起点任务，用集合T

第二类：终点任务，用集合T

第三类：布尔约束“与”任务，用集合T

第四类：布尔约束“或”任务，分别用集合

第五类：布尔约束“非”任务，用集合T

那么将所有任务用布尔约束描述为：

步骤三：根据任务要求更新邻接矩阵；

将邻接矩阵中所有布尔约束“非”任务所在行和列均设置为∞，即：

W(12，：)＝∞，W(：，12)＝∞，W(15，：)＝∞，W(：，15)＝

∞，...，W(21，：)＝∞，W(：，21)＝∞；即更新W(12，11)＝∞，

W(12，12)＝∞，W(12，13)＝∞，W(11，12)＝∞，W(13，12)＝∞，

W(15，15)＝∞，W(15，16)＝∞，W(16，15)＝∞，W(21，20)＝∞，

W(21，21)＝∞，W(21，22)＝∞，W(20，21)＝∞，W(22，21)＝∞；

步骤四：计算任务间的最短距离和对应的路径并储存；

根据邻接矩阵W利用Dijkstra算法计算两个空间之间的最短移动距离和对应的路径，计算从源点R

1)创建两个集合S、U和一个1×m的全0矩阵P，其中S是已经找到最短路径的顶点，U是还待计算的顶点，令S＝R

2)将集合U中具有最小距离的顶点R

3)更新集合U中顶点的距离，若从源点R

4)若目标点R

5)根据矩阵P通过回溯法求解路径l

利用上述的Dijkstra算法分别计算集合T

R

R

R

计算本实施例的d

d

d

d

表1

需要主要的是，从源点R

步骤五：随机产生一个满足布尔约束任务要求的初始任务序列，并计算它的最短移动距离及其对应的路径；

参照图4，根据布尔约束的任务要求，选择所有“与”任务并在每个“或”任务中选择一个任务组成中途任务序列，如：

R

L＝{R

并作如下操作：

最优任务序列：M

最优任务序列的最短移动距离：D

最优任务序列的最短移动距离对应的路径：L

步骤六：对初始任务序列进行模拟退火算法优化；

对初始任务序列进行模拟退火操作，从初始温度

第一种操作，两点交换操作：

在任务序列M＝{R

第二种操作，倒序操作：

在任务序列M＝{R

第三种操作，重插入操作：

在“或”任务中随机，1≤k≤3，并从任务集合

在得到新的任务序列M

如果新的任务序列M

另外，如新的任务序列M

M

如果新的任务序列M

M＝M

在本实施例中，在每个温度下进行10次搜索认为在该温度下已经充分搜索，温度衰减至下一温度进行搜索；

步骤七：输出最优任务序列、最短移动距离及其对应的路径；

本实施例中，当温度降低到终止温度

在本实施例中，对于给定的全局环境和基于布尔约束的任务要求，一共有3*3*2种“或”任务选择情况，对于“与”任务和选定的“或”任务(共6个任务)的排列情况有