CN112764413B - 一种机器人路径规划方法 - Google Patents
一种机器人路径规划方法 Download PDFInfo
- Publication number
- CN112764413B CN112764413B CN201911005993.0A CN201911005993A CN112764413B CN 112764413 B CN112764413 B CN 112764413B CN 201911005993 A CN201911005993 A CN 201911005993A CN 112764413 B CN112764413 B CN 112764413B
- Authority
- CN
- China
- Prior art keywords
- node
- path
- algorithm
- corner
- list
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 30
- 238000004387 environmental modeling Methods 0.000 claims description 3
- 230000001351 cycling effect Effects 0.000 claims 1
- 238000005265 energy consumption Methods 0.000 abstract description 5
- 238000010586 diagram Methods 0.000 description 4
- 238000005457 optimization Methods 0.000 description 2
- 230000001133 acceleration Effects 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 230000007613 environmental effect Effects 0.000 description 1
- 238000007726 management method Methods 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 230000002787 reinforcement Effects 0.000 description 1
- 239000002699 waste material Substances 0.000 description 1
Classifications
-
- G—PHYSICS
- G05—CONTROLLING; REGULATING
- G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
- G05D1/02—Control of position or course in two dimensions
- G05D1/021—Control of position or course in two dimensions specially adapted to land vehicles
- G05D1/0212—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory
- G05D1/0221—Control of position or course in two dimensions specially adapted to land vehicles with means for defining a desired trajectory involving a learning process
Landscapes
- Engineering & Computer Science (AREA)
- Aviation & Aerospace Engineering (AREA)
- Radar, Positioning & Navigation (AREA)
- Remote Sensing (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Automation & Control Theory (AREA)
- Manipulator (AREA)
- Control Of Position, Course, Altitude, Or Attitude Of Moving Bodies (AREA)
Abstract
本发明涉及一种机器人路径规划方法，包括：环境建模；基于算法，搜索一条从起始位置到目标位置的最短路径；如果搜索得到的最短路径唯一，则将搜索的最短路径作为最终的规划路径，如果存在多条最短路径，则从中确定一条拐角最少的路径作为最终的规划路径。本发明提供的方法，相比于传统技术，不仅能够搜索一条最短路径，并且在存在多条最短路径时，能从中选择一条拐角最少的路径，从而降低机器人运动的时间和能耗。
Description
技术领域
本发明涉及机器人智能技术领域，尤其是涉及一种机器人路径规划方法。
背景技术
移动机器人路径规划是指基于某些特定准则，在环境中存在障碍物的前提下，搜索一条从起始位置到目标位置的安全、无碰撞的最短路径。
发明人在研究中发现，现有机器人路径规划方法只能进行搜索最短路径的处理，当存在多条最短路径时，如果选择的路径其拐角较多时，机器人在每次转弯，都要进行一次减速、加速的操作，因此行进的耗时也会增加，能耗也会增加，并不利于资源的最优管理。
发明内容
有鉴于此，有必要针对上述的问题，提供一种机器人路径规划方法，相比于传统技术，不仅能够搜索一条最短路径，并且在存在多条最短路径时，能从中选择一条拐角最少的路径，从而降低机器人运动的时间和能耗。
一种机器人路径规划方法，包括：
环境建模；
基于算法，搜索一条从起始位置到目标位置的最短路径；
如果搜索得到的最短路径唯一，则将搜索的最短路径作为最终的规划路径，如果存在多条最短路径，则从中确定一条拐角最少的路径作为最终的规划路径。
所述环境建模的方法，包括栅格法。
所述方法包括：
基于栅格法进行环境建模；
基于改进A*算法获取一条从起始位置到目标位置的最短路径，且同时满足拐角最少的条件。
所述方法具体包括：
1)采用栅格法进行环境建模；
2)设置一个open列表和close列表，并将起始节点放入open列表中；
3)遍历搜索open列表中存在的节点，根据启发函数确定代价f(n)大小，启发函数如下：
f(n)＝g(n)+h(n)；其中，g(n)为当前点与起始节点之间的移动代价；h(n)为当前点与目标节点之间的移动代价。将f(n)值最小的节点n作为算法路径选择的下一个节点，将该节点从open列表中删除并添加到close列表；若存在多个f(n)值最小的节点，则比较其已行路径的拐角次数，选择拐角次数最少的点作为下一个节点；
4)判断节点n是否为目标节点，若为目标节点，则结束算法；否则，则进行下一步；
5)搜索节点n邻域内所有符合搜索要求的子节点m，计算所有待搜索节点的f(m)值，选择f(m)值最小的节点m作为算法路径选择的下一个节点；
6)若节点m不在open列表和close列表中，则将其添加到open列表中，并为子节点m添加一个指针指向其父节点n；若节点m在open列表中，则对比之前存储在open列表中的函数值，保留函数值小的数值；若节点在close列表中，则该节点已在当前最优路径上，返回上一步继续对比扩展其他子节点；
7)循环步骤3)至步骤6)，但算法寻找到目标节点或open列表为空时，结束算法。
在所述算法中，拐角的判断方法为：
对于只允许规划直线的A*算法，获取当前节点的横坐标与纵坐标以及当前节点的父节点的父节点的横坐标与纵坐标，当两点的横坐标与纵坐标均不同时，则说明路径出现了拐角。
在所述算法中，拐角的判断方法为：
对于允许规划斜线的A*算法，需要获取当前节点A的坐标(A1,A2)，节点A的父节点B的坐标(B1,B2)，以及节点B的父节点C的坐标(C1,C2)，当A1-B1≠B1-C1且A2-B2≠B2-C2，则说明路径出现了拐角。
本发明提供的方法，相比于传统技术，不仅能够搜索一条最短路径，并且在存在多条最短路径时，能从中选择一条拐角最少的路径，从而降低机器人运动的时间和能耗。
附图说明
图1是本发明实施例中提供的一种机器人路径规划方法的流程示意图；
图2是本发明实施例中算法不允许斜行的情况下，算法优化前的搜索路径示意图；
图3是本发明相对于图2，在算法不允许斜行的情况下，算法优化后的搜索路径示意图；
图4是本发明实施例中算法允许斜行的情况下，算法优化前的搜索路径示意图；
图5是本发明相对于图4，在算法允许斜行的情况下，算法优化后的搜索路径示意图。
具体实施方式
下面将结合本发明中的附图，对本发明中的技术方案进行清楚、完整的描述。基于本发明中的操作流程和加强方法，本领域技术人员在没有做出创造性劳动前提下所获得的所有其他工具，都属于本发明保护的范围。
现有技术中，移动机器人路径规划算法主要存在的问题是：随着环境复杂程度的提升，不可避免地出现多条长度相同、拐角数量不同的的路径。由于移动机器人每次转弯，都需要进行一次减速、加速的操作，因此在路径长度相同的情况下，拐角数量多的路径，移动机器人完成路径的行走的总耗时也会增加，造成能源的浪费。
在本发明的一个实施例中，如图1，算法设计：
1)采用栅格法进行环境建模；
2)设置一个open列表和close列表，并将起始节点放入open列表中；
3)遍历搜索open列表中存在的节点，根据启发函数确定代价f(n)大小，启发函数如下：
f(n)＝g(n)+h(n)；其中，g(n)为当前点与起始节点之间的移动代价；h(n)为当前点与目标节点之间的移动代价。将f(n)值最小的节点n作为算法路径选择的下一个节点，将该节点从open列表中删除并添加到close列表；若存在多个f(n)值最小的节点，则比较其已行路径的拐角次数，选择拐角次数最少的点作为下一个节点；
4)判断节点n是否为目标节点，若为目标节点，则结束算法；否则，则进行下一步；
5)搜索节点n邻域内所有符合搜索要求的子节点m，计算所有待搜索节点的f(m)值，选择f(m)值最小的节点m作为算法路径选择的下一个节点；
6)若节点m不在open列表和close列表中，则将其添加到open列表中，并为子节点m添加一个指针指向其父节点n；若节点m在open列表中，则对比之前存储在open列表中的函数值，保留函数值小的数值；若节点在close列表中，则该节点已在当前最优路径上，返回上一步继续对比扩展其他子节点；
7)循环步骤3)至步骤6)，但算法寻找到目标节点或open列表为空时，结束算法。
拐角的判断方法：
对于只允许规划直线的A*算法，获取当前节点的横坐标与纵坐标以及当前节点的父节点的父节点的横坐标与纵坐标，当两点的横坐标与纵坐标均不同时，则说明路径出现了拐角；对比图为图2和图3。
对于允许规划斜线的A*算法，需要获取当前节点A的坐标(A1,A2)，节点A的父节点B的坐标(B1,B2)，以及节点B的父节点C的坐标(C1,C2)，当A1-B1≠B1-C1且A2-B2≠B2-C2，则说明路径出现了拐角。具体对比图参见图4和图5。
综上所述，本发明提供的机器人路径规划方法，其技术思路为：
环境建模；
基于算法，搜索一条从起始位置到目标位置的最短路径；
如果搜索得到的最短路径唯一，则将搜索的最短路径作为最终的规划路径，如果存在多条最短路径，则从中确定一条拐角最少的路径作为最终的规划路径。
上述机器人路径规划方法，相比于传统技术，不仅能够搜索一条最短路径，并且在存在多条最短路径时，能从中选择一条拐角最少的路径，从而降低机器人运动的时间和能耗。
以上所述实施例仅表达了本发明的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对本发明专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干变形和改进，这些都属于本发明的保护范围。因此，本发明专利的保护范围应以所附权利要求为准。
Claims (2)
1.一种机器人路径规划方法，其特征在于，包括：
环境建模；
基于改进A*算法获取一条从起始位置到目标位置的最短路径，如果搜索得到的最短路径唯一，则将搜索的最短路径作为最终的规划路径，如果存在多条最短路径，则从中确定一条拐角最少的路径作为最终的规划路径，具体包括以下步骤：
(1)设置一个open列表和close列表，并将起始节点放入open列表中；
(2)遍历搜索open列表中存在的节点，根据启发函数确定代价f(n)大小，启发函数如下：
f(n)＝g(n)+h(n)
其中，g(n)为当前点与起始节点之间的移动代价；h(n)为当前点与目标节点之间的移动代价；将f(n)值最小的节点n作为算法路径选择的下一个节点，将该节点从open列表中删除并添加到close列表；若存在多个f(n)值最小的节点，则比较其已行路径的拐角次数，选择拐角次数最少的点作为下一个节点，拐角的判断方法为：
对于只允许规划直线的A*算法，获取当前节点的横坐标与纵坐标以及当前节点的父节点的父节点的横坐标与纵坐标，当两点的横坐标与纵坐标均不同时，则说明路径出现了拐角；
对于允许规划斜线的A*算法，需要获取当前节点A的坐标(A1,A2)，节点A的父节点B的坐标(B1,B2)，以及节点B的父节点C的坐标(C1,C2)，当A1-B1≠B1-C1且A2-B2≠B2-C2，则说明路径出现了拐角；
(3)判断节点n是否为目标节点，若为目标节点，则结束算法；否则，则进行下一步；
(4)搜索节点n邻域内所有符合搜索要求的子节点m，计算所有待搜索节点的f(m)值，选择f(m)值最小的节点m作为算法路径选择的下一个节点；
(5)若节点m不在open列表和close列表中，则将其添加到open列表中，并为子节点m添加一个指针指向其父节点n；若节点m在open列表中，则对比之前存储在open列表中的函数值，保留函数值小的数值；若节点在close列表中，则该节点已在当前最优路径上，返回上一步继续对比扩展其他子节点；
(6)循环步骤(2)至步骤(5)，当算法寻找到目标节点或open列表为空时，结束算法。
2.根据权利要求1所述的机器人路径规划方法，其特征在于，所述环境建模的方法，具体为栅格法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201911005993.0A CN112764413B (zh) | 2019-10-22 | 2019-10-22 | 一种机器人路径规划方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201911005993.0A CN112764413B (zh) | 2019-10-22 | 2019-10-22 | 一种机器人路径规划方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN112764413A CN112764413A (zh) | 2021-05-07 |
| CN112764413B true CN112764413B (zh) | 2024-01-16 |
Family
ID=75691928
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201911005993.0A Active CN112764413B (zh) | 2019-10-22 | 2019-10-22 | 一种机器人路径规划方法 |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN112764413B (zh) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN113156970B (zh) * | 2021-05-08 | 2023-06-09 | 珠海一微半导体股份有限公司 | 一种通行区域的路径融合规划方法、机器人及芯片 |
Citations (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103344248A (zh) * | 2013-07-16 | 2013-10-09 | 长春理工大学 | 一种车辆导航系统的最佳路径计算方法 |
| CN105955280A (zh) * | 2016-07-19 | 2016-09-21 | Tcl集团股份有限公司 | 移动机器人路径规划和避障方法及系统 |
| CN107990903A (zh) * | 2017-12-29 | 2018-05-04 | 东南大学 | 一种基于改进a*算法的室内agv路径规划方法 |
| CN108413976A (zh) * | 2018-01-23 | 2018-08-17 | 大连理工大学 | 一种面向多工况的爬壁机器人智能路径规划方法及系统 |
| CN108444488A (zh) * | 2018-02-05 | 2018-08-24 | 天津大学 | 基于等步采样a*算法的无人驾驶局部路径规划方法 |
| CN108469827A (zh) * | 2018-05-16 | 2018-08-31 | 江苏华章物流科技股份有限公司 | 一种适用于物流仓储系统的自动导引车全局路径规划方法 |
| CN109764886A (zh) * | 2019-01-15 | 2019-05-17 | 成都信息工程大学 | 一种路径规划方法 |
| CN109798909A (zh) * | 2019-02-01 | 2019-05-24 | 安徽达特智能科技有限公司 | 一种全局路径规划的方法 |
| CN109839935A (zh) * | 2019-02-28 | 2019-06-04 | 华东师范大学 | 多agv的路径规划方法及设备 |
| CN109947098A (zh) * | 2019-03-06 | 2019-06-28 | 天津理工大学 | 一种基于机器学习策略的距离优先最佳路径选择方法 |
-
2019
- 2019-10-22 CN CN201911005993.0A patent/CN112764413B/zh active Active
Patent Citations (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103344248A (zh) * | 2013-07-16 | 2013-10-09 | 长春理工大学 | 一种车辆导航系统的最佳路径计算方法 |
| CN105955280A (zh) * | 2016-07-19 | 2016-09-21 | Tcl集团股份有限公司 | 移动机器人路径规划和避障方法及系统 |
| CN107990903A (zh) * | 2017-12-29 | 2018-05-04 | 东南大学 | 一种基于改进a*算法的室内agv路径规划方法 |
| CN108413976A (zh) * | 2018-01-23 | 2018-08-17 | 大连理工大学 | 一种面向多工况的爬壁机器人智能路径规划方法及系统 |
| CN108444488A (zh) * | 2018-02-05 | 2018-08-24 | 天津大学 | 基于等步采样a*算法的无人驾驶局部路径规划方法 |
| CN108469827A (zh) * | 2018-05-16 | 2018-08-31 | 江苏华章物流科技股份有限公司 | 一种适用于物流仓储系统的自动导引车全局路径规划方法 |
| CN109764886A (zh) * | 2019-01-15 | 2019-05-17 | 成都信息工程大学 | 一种路径规划方法 |
| CN109798909A (zh) * | 2019-02-01 | 2019-05-24 | 安徽达特智能科技有限公司 | 一种全局路径规划的方法 |
| CN109839935A (zh) * | 2019-02-28 | 2019-06-04 | 华东师范大学 | 多agv的路径规划方法及设备 |
| CN109947098A (zh) * | 2019-03-06 | 2019-06-28 | 天津理工大学 | 一种基于机器学习策略的距离优先最佳路径选择方法 |
Also Published As
| Publication number | Publication date |
|---|---|
| CN112764413A (zh) | 2021-05-07 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN109115226B (zh) | 基于跳点搜索的多机器人冲突避免的路径规划方法 | |
| CN115079705B (zh) | 基于改进a星融合dwa优化算法的巡检机器人路径规划方法 | |
| CN107167154B (zh) | 一种基于时间代价函数的时间窗路径规划冲突解决方法 | |
| CN113074728B (zh) | 基于跳点寻路与协同避障的多agv路径规划方法 | |
| CN110487290B (zh) | 基于变步长a星搜索的无人驾驶汽车局部路径规划方法 | |
| WO2018090769A1 (zh) | 路径识别方法和系统 | |
| CN114690787B (zh) | 一种多移动机器人路径规划方法、系统、计算机设备及存储介质 | |
| CN114428499A (zh) | 一种融合Astar与DWA算法的移动小车路径规划方法 | |
| CN114281080B (zh) | 一种amr调度系统中解死锁的方法 | |
| CN109341698B (zh) | 一种移动机器人的路径选择方法及装置 | |
| Liu et al. | Warehouse‐Oriented Optimal Path Planning for Autonomous Mobile Fire‐Fighting Robots | |
| CN109816131B (zh) | 路径规划方法、路径规划装置及计算机可读存储介质 | |
| CN112764413B (zh) | 一种机器人路径规划方法 | |
| CN112633590B (zh) | 一种用于四向穿梭车的智能入库方法及系统 | |
| CN113532443A (zh) | 路径规划方法、装置、电子设备及介质 | |
| CN113485328A (zh) | 一种全覆盖路径规划方法、装置、电子设备和存储介质 | |
| Fan et al. | Research and implementation of multi-robot path planning based on genetic algorithm | |
| CN113985892B (zh) | 一种基于改进a＊算法的智能船舶路径规划方法 | |
| CN114564023B (zh) | 一种动态场景下的跳点搜索路径规划方法 | |
| CN112633606B (zh) | 一种多agv路径规划方法、装置及计算机可读存储介质 | |
| CN117570981A (zh) | 基于安全区间的多机器人路径规划方法 | |
| CN116907490A (zh) | 一种基于冲突搜索的多机器人路径规划方法 | |
| Riman et al. | A Priority-based Modified A∗ Path Planning Algorithm for Multi-Mobile Robot Navigation | |
| CN111912407B (zh) | 一种多机器人系统的路径规划方法 | |
| CN114281087B (zh) | 基于终身规划a*和速度障碍法的路径规划方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |