Fast Four-Stage Local Motion Planning Method for Mobile Robot

doi:10.1007/s12204-022-2423-8

Abstract

Abstract: Mobile robot local motion planning is responsible for the fast and smooth obstacle avoidance, which is one of the main indicators for evaluating mobile robots’ navigation capabilities. Current methods formulate local motion planning as a unified problem; therefore it cannot satisfy the real-time requirement on the platform with limited computing ability. In order to solve this problem, this paper proposes a fast local motion planning method that can reach a planning frequency of 500 Hz on a low-cost CPU. The proposed method decouples the local motion planning as the front-end path searching and the back-end optimization. The front-end is composed of the environment topology analysis and graph searching. The back-end includes dynamically feasible trajectory generation and optimal trajectory selection. Different from the popular methods, the proposed method decomposes the local motion planning into four sub-modules, each of which aims to solve one problem. Combining four submodules, the proposed method can obtain the complete local motion planning algorithm which can fast generate a smooth and collision-free trajectory. The experimental results demonstrate that the proposed method has the ability to obtain the smooth, dynamically feasible and collision-free trajectory and the speed of the planning is fast.

Key words: robotics, path planning, trajectory generation, smooth trajectory planning

摘要： 局部轨迹规划承担着移动机器人快速、平滑避障的功能，是评估移动机器人导航能力的主要指标之一。目前的方法把局部轨迹规划的各项要求表示成统一的问题进行求解，在计算能力受限时，基本上不能满足实时性。针对上述情况，本文提出了一种在低成本处理器上运行速度可以达到500 Hz的快速局部轨迹规划算法。把轨迹规划问题分为前端搜索和后端优化两个部分，其中前端搜索部分包括环境拓扑分析和图搜索，后端部分包括满足运动学约束的轨迹生成和最优轨迹的选取。与目前大多数方法不同，本文把轨迹规划问题分解成四个子模块，每一个子模块只考虑一个问题。通过四个子模块组合形成一个完整的规划算法，该算法快速地生成一条平滑、无碰撞的轨迹。实验证明提出的方法可以生成平滑且满足运动学约束的安全轨迹，并且有较快的规划速度。

关键词: 机器人，路径规划，轨迹生成，平滑轨迹规划

CLC Number:

TP301.1

HUANG Shan(黄山), HUANG Hongzhong(黄洪钟), ZENG Qi(曾奇). Fast Four-Stage Local Motion Planning Method for Mobile Robot[J]. J Shanghai Jiaotong Univ Sci, 2024, 29(3): 428-435.

References

[1] WANG M C. Path planning of mobile robots based on A? algorithm [D]. Shenyang, China: Shenyang University of Technology, 2017 (in Chinese).
[2] DIJKSTRA E W. A note on two problems in connexion with graphs [J]. Numerische Mathematik, 1959, 1(1): 269-271.
[3] ZHANG J, CHADHA R G, VELIVELA V, et al. PCAP: Pre-computed alternative paths to enable aggressive aerial maneuvers in cluttered environments [C]//2018 IEEE/RSJ International Conference on Intelligent Robots and Systems. Madrid, Spain: IEEE, 2018: 8456-8463.
[4] HOWARD T, PIVTORAIKO M, KNEPPER R A, et al. Model-predictive motion planning: Several key developments for autonomous mobile robots [J]. IEEE Robotics & Automation Magazine, 2014, 21(1): 64-73.
[5] MICELLI P, LIKHACHEV M. FOCS: Planning by fusion of optimal control & search and its application to navigation [C]//2018 IEEE/RSJ International Conference on Intelligent Robots and Systems. Madrid, Spain: IEEE, 2018: 8082-8088.
[6] KUFFNER J J, LAVALLE S M. RRT-connect: An efficient approach to single-query path planning [C]//2000 IEEE International Conference on Robotics and Automation. San Francisco, CA, USA: IEEE, 2000: 995-1001.
[7] HSU D, KAVRAKI L E, LATOMBE J C, et al. On finding narrow passages with probabilistic roadmap planners[C]//1998 3rd Workshop on the Algorithmic Foundations of Robotics. Natick, MA, USA: A K Peters, 1998: 141-153.
[8] KARAMAN S, FRAZZOLI E. Sampling-based algorithms for optimal motion planning [J]. The International Journal of Robotics Research, 2011, 30(7): 846-894.
[9] GAMMELL J D, SRINIVASA S S, BARFOOT T D. Informed RRT?: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic [C]//2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. Chicago, IL, USA: IEEE, 2014: 2997-3004.
[10] VON′ASEK V, PˇENIˇCKA R, KOZL′IKOV′A B. Computing multiple guiding paths for sampling-based motion planning [C]//2019 19th International Conference on Advanced Robotics. Belo Horizonte, Brazil: IEEE, 2019: 374-381.
[11] LI J X, DAI B, LI X H, et al. A real-time and predictive trajectory-generation motion planner for autonomous ground vehicles [C]//2017 9th International Conference on Intelligent Human-Machine Systems and Cybernetics. Hangzhou, China: IEEE, 2017: 108-113.
[12] PADEN B, ˇC′AP M, YONG S Z, et al. A survey of motion planning and control techniques for self-driving urban vehicles [J]. IEEE Transactions on Intelligent Vehicles, 2016, 1(1): 33-55.
[13] MELLINGER D, KUMAR V. Minimum snap trajectory generation and control for quadrotors [C]//2011 IEEE International Conference on Robotics and Automation. Shanghai, China: IEEE, 2011: 2520-2525.
[14] RICHTER C, BRY A, ROY N. Polynomial trajectory planning for aggressive quadrotor flight in dense indoor environments [M]//Robotics Research, Cham: Springer, 2016: 649-666.
[15] GAO F, WU W, LIN Y, et al. Online safe trajectory generation for quadrotors using fast marching method and Bernstein basis polynomial [C]//2018 IEEE International Conference on Robotics and Automation. Brisbane, Australia: IEEE, 2018: 344-351.
[16] LUO S S, LI X H, SUN Z P. An optimization-based motion planning method for autonomous driving vehicle [C]//2020 3rd International Conference on Unmanned Systems. Harbin, China: IEEE, 2020: 739-744.
[17] ZHOU B Y, GAO F, PAN J, et al. Robust real-time UAV replanning using guided gradient-based optimization and topological paths [C]//2020 IEEE International Conference on Robotics and Automation. Paris, France: IEEE, 2020: 1208-1214.
[18] SIM′EON T, LAUMOND J P, NISSOUX C. Visibilitybased probabilistic roadmaps for motion planning [J]. Advanced Robotics, 2000, 14(6): 477-493.
[19] HESS W, KOHLER D, RAPP H, et al. Real-time loop closure in 2D LIDAR SLAM [C]//2016 IEEE International Conference on Robotics and Automation. Stockholm, Sweden: IEEE, 2016: 1271-1278.
[20] SAARINEN J, ANDREASSON H, STOYANOV T, et al. Normal distributions transform Monte-Carlo localization (NDT-MCL) [C]//2013 IEEE/RSJ International Conference on Intelligent Robots and Systems. Tokyo, Japan: IEEE, 2013: 382-389.
[21] AHN J, SHIN S, KIM M, et al. Accurate path tracking by adjusting look-ahead point in pure pursuit method [J]. International Journal of Automotive Technology, 2021, 22(1): 119-129.
[22] LI X H, SUN Z P, CAO D P, et al. Development of a new integrated local trajectory planning and tracking control framework for autonomous ground vehicles [J]. Mechanical Systems and Signal Processing, 2017, 87: 118-137.
[23] KELLY A, NAGY B. Reactive nonholonomic trajectory generation via parametric optimal control [J]. The International Journal of Robotics Research, 2003, 22(7/8): 583-601.
[24] R ¨OSMANN C, HOFFMANN F, BERTRAM T. Planning of multiple robot trajectories in distinctive topologies [C]//2015 European Conference on Mobile Robots. Lincoln, UK: IEEE, 2015: 1-6.