Hierarchical Motion Planning Method Based on Hybrid A-star for Cruising in Parking Area

doi:10.3901/JME.2023.24.290

Abstract

Abstract: As an important part of the intelligent transportation system, autonomous vehicles have received more and more attention from researchers. Auto valet parking is an essential part of high-level autonomous driving. As valet parking is applied to unstructured environments, researchers need to design special planning algorithms to deal with the various challenges of unstructured scenarios such as the lack of road lines, and the uncertain forecasts of surroundings. Considering the environmental characteristics of valet parking, a hierarchical motion planning method based on an improved hybrid A-Star algorithm and a time elastic band algorithm is proposed. By modifying the collision detection process, the hybrid A-Star algorithm can achieve interactive behavior. By introducing the cost of the reference line, the search efficiency of the hybrid A-Star algorithm is improved. The improved hybrid A-Star algorithm can generate reasonable and effective initial trajectories for unstructured environments. The time-elastic-band algorithm has high execution efficiency, effectively solves the problem of vehicle kinematics and obstacle constraints, and can quickly respond to environmental changes. A real vehicle experiment is carried out in Suzhou, China. The results show that the proposed algorithm can effectively solve the problem of vehicle lateral motion planning in conventional scenarios.

Key words: auto valet parking, motion planning, hybrid A-star, timed-elastic-band

CLC Number:

U463

ZHAO Jintao, LI Liang, XUE Zhongjin, ZHANG Zhihuang. Hierarchical Motion Planning Method Based on Hybrid A-star for Cruising in Parking Area[J]. Journal of Mechanical Engineering, 2023, 59(24): 290-298.

References

[1] FIGUEIREDO L,JESUS I,MACHADO J T,et al Towards the development of intelligent transportation systems[C]//ITSC 2001. 2001 IEEE Intelligent Transportation Systems. Proceedings (Cat. No. 01TH8585). Oakland,CA,USA. New York:IEEE,2001:1206-1211.
[2] LÖPER C,BRUNKEN C,THOMAIDIS G,et al. Automated valet parking as part of an integrated travel assistance[C]//16th International IEEE Conference on Intelligent Transportation Systems (ITSC 2013). The Hague,Netherlands. New York:IEEE,2013:2341-2348.
[3] ZIPS P,BOCK M,KUGI A. A fast motion planning algorithm for car parking based on static optimization[C]//2013 IEEE/RSJ International Conference on Intelligent Robots and Systems. Tokyo,Japan. New York:IEEE,2013:2392-2397.
[4] LI Bai,SHAO Zhijiang. A unified motion planning method for parking an autonomous vehicle in the presence of irregularly placed obstacles[J]. Knowledge-Based Systems,2015,86:11-20.
[5] LI Bai,ZHANG Youmin,SHAO Zhijiang,et al. Simultaneous versus jointcomputing:A case study of multi-vehicle parking motion planning[J]. Journal of Computational Science,2017,20:30-40.
[6] BANZHAF H,NIENHÜSER D,KNOOP S,et al. The future of parking:A survey on automated valet parking with an outlook on high density parking[C]//2017 IEEE Intelligent Vehicles Symposium (IV). Los Angeles,CA,USA. New York:IEEE,2017:1827-1834.
[7] KLAUDT S,ZLOCKI A,ECKSTEIN L. A-priori map information and path planning for automated valet-parking[C]//2017 IEEE Intelligent Vehicles Symposium (IV). Los Angeles,CA,USA. New York:IEEE,2017:1770-1775.
[8] LIKHACHEV M,FERGUSON D. Planning long dynamically feasible maneuvers for autonomous vehicles[J]. The International Journal of Robotics Research,2009,28(8):933-945.
[9] FERGUSON D,HOWARD T M,LIKHACHEV M. Motion planning in urban environments[J]. Journal of Field Robotics,2008,25(11-12):939-960.
[10] YU Luyang,JIANG Haobin,HUA Lei. Anti-congestion route planning scheme based on Dijkstra algorithm for automatic valet parking system[J]. Applied Sciences,2019,9(23):5016.
[11] PETEREIT J,EMTER T,FREY C W,et al. Application of hybrid A* to an autonomous mobile robot for path planning in unstructured outdoor environments[C]//Robotik 2012,7th German Conference on Robotics. Munich,Germany. VDE,2012:1-6.
[12] KAVRAKI L E,SVESTKA P,LATOMBE J C,et al. Probabilistic roadmaps for path planning in high-dimensional configuration spaces[J]. IEEE Transactions on Robotics and Automation,1996,12(4):566-580.
[13] LAVALLE S M. Rapidly-exploring random trees:A new tool for path planning[R]. Ames:Lowa State University,1998.
[14] KUWATA Y,TEO J,FIORE G,et al. Real-time motion planning with applications to autonomous urban driving[J]. IEEE Transactions on Control Systems Technology,2009,17(5):1105-1118.
[15] RÖSMANN C,HOFFMANN F,BERTRAM T. Integrated online trajectory planning and optimization in distinctive topologies[J]. Robotics and Autonomous Systems,2017,88:142-153.
[16] LIM W,LEE S,SUNWOO M,et al. Hierarchical trajectory planning of an autonomous car based on the integration of a sampling and an optimization method[J]. IEEE Transactions on Intelligent Transportation Systems,2018,19(2):613-626.
[17] DAI Siyu,WANG Yebin. Long-horizon motion planning for autonomous vehicle parking incorporating incomplete map information[C]//2021 IEEE International Conference on Robotics and Automation (ICRA). Xi'an,China. New York:IEEE,2021:8135-8142.
[18] LI Chao,LI Xiaohui,LI Junxiang,et al. Trajectory planning for autonomous ground vehicles driving in structured environments[C]//20179th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC). Hangzhou,China. New York:IEEE,2017,2:41-46.
[19] FAN Haoyang,ZHU Fan,LIU Changchun,et al. Baidu apollo em motion planner[J]. arXiv preprint arXiv:1807. 08048,2018.
[20] DOLGOV D,THRUN S,MONTEMERLO M,et al. Practical search techniques in path planning for autonomous driving[J]. Ann Arbor,2008,1001(48105):18-80.
[21] SEDIGHI S,NGUYEN D V,KUHNERT K D. Guided hybrid A-star path planning algorithm for valet parking applications[C]//20195th International Conference on Control,Automation and Robotics (ICCAR). Beijing,China. New York:IEEE,2019:570-575.
[22] REEDS J,SHEEP L. Optimal paths for a car that goes both forwards and backwards[J]. Pacific Journal of Mathematics,1990,145(2):367-393.
[23] RÖSMANN C,FEITEN W,WÖSCH T,et al. Efficient trajectory optimization using a sparse model[C]//2013 European Conference on Mobile Robots. Barcelona,Spain. New York:IEEE,2013:138-143.
[24] KÜMMERLE R,GRISETTI G,STRASDAT H,et al. G 2 o:A general framework for graph optimization[C]//2011 IEEE International Conference on Robotics and Automation. Shanghai,China. New York:IEEE,2011:3607-3613.