计算机工程与应用 ›› 2017, Vol. 53 ›› Issue (18): 17-23.DOI: 10.3778/j.issn.1002-8331.1706-0195

• 热点与综述 • 上一篇    下一篇

导航系统中多目标路径平滑化规划的研究

孙梦娜,杨如民,余成波   

  1. 重庆理工大学 远程测试与控制研究所,重庆 400054
  • 出版日期:2017-09-15 发布日期:2017-09-29

Research on multi-objective path-smoothing planning in navigation system

SUN Mengna, YANG Rumin, YU Chengbo   

  1. Institute of Remote Test and Control, Chongqing University of Technology, Chongqing 400054, China
  • Online:2017-09-15 Published:2017-09-29

摘要: 路径规划是车辆、机器人出行、无人机航路推荐和计算机游戏等许多应用中的关键任务。现有的大多路径规划常简化为单目标优化问题进行求解。但在现实生活中,还需要同时考虑多种规划目标,且用于规划路径的目标之间还存在着彼此不能变换的问题。在熟知的路径规划算法(D*Lite)上提出了一种新的多目标路径平滑化规划算法—平滑多目标D*Lite算法。通过构造一条初始多目标平滑路径,当检测到环境变化时采用增量搜索思想,仅更新受影响结点并从当前结点重新进行规划得到一条新的多目标平滑路径。仿真结果表明,该算法不但能有效躲避突发障碍物,规划路径拐点较少,还能提高搜索效率,可有效应用于具有不同非交互规划目标的导航系统。

关键词: 多目标优化, 导航系统, 动态路径规划, 增量路径规划, 方向性

Abstract: Path planning are the key tasks in many applications such as vehicles, robotic trips, UAV path recommendations and computer games. Most of the existing path planning algorithms are often simplified as single objective optimization problems. However, multiple planning objectives which can’t transform to each other have to be taken into consideration in reality. Based on the known path planning algorithm (D*Lite), this paper proposes a new multi-objective path-smoothing planning algorithm named smoothing multi-objective D*Lite algorithm. This algorithm needs to construct an initial multi-objective smoothing path, when it detects changes of the environment, only the affected nodes are updated and a new multi-objective smoothing path is re-planned from the current node by adopting the incremental search thought. The simulation results show that the proposed algorithm can not only avoid unexpected obstacles with effect, have less inflection point on the planning path and improve searching efficiency, but also can be applied to the navigation system with different non-interactive planning objectives effectively.

Key words: multi-objective optimization, navigation system, dynamic path planning, incremental path planning, directivity