High-performance Trajectory Optimization for Automated Parking via Half-space Constraining Theory

doi:10.3901/JME.2024.10.273

Abstract

Abstract: Trajectory planning is a vital function in vehicular automatic parking systems. Existing algorithms for automatic parking trajectory planning fail to balance generalizability, precision, time efficiency, and solution optimality. Numerical-optimization-based trajectory planning is considered in this work. Initially, the concerned planning task is formulated as a unified optimal control problem. Subsequently, a half-space constraining theory is introduced, together with a reference trajectory and a trust-region constraint modeling method, to simplify the nominal large-scale and nonconvex collision-avoidance constraints as linear inequalities. Finally, the simplified optimal control problem is solved numerically to derive an optimal parking trajectory. We name this proposed planner predefined space rapid optimization (PSRO) method. Extensive simulations indicate that PSRO outperforms prevalent trajectory optimizers such as OBCA and LIOM with respect to success rate, solution quality, and computational speed.

Key words: automated parking, trajectory planning, computational optimal control, nonlinear program, intelligent vehicle

CLC Number:

U469

CHEN Xiaoming, LI Bai, FAN Lili, WANG Yazhou, ZHANG Tantan, ZHANG Youmin, CAO Dongpu. High-performance Trajectory Optimization for Automated Parking via Half-space Constraining Theory[J]. Journal of Mechanical Engineering, 2024, 60(10): 273-288.

References

[1] 杜明博，梅涛，陈佳佳，等. 复杂环境下基于RRT的智能车辆运动规划算法[J]. 机器人，2015，37(4):443-450. DU Mingbo，MEI Tao，CHEN Jiajia，et al. RRT-based motion planning algorithm for intelligent vehicle in complex environments[J]. Robot，2015，37(4):443-450.
[2] 胡宇辉，王旭，胡家铭，等. 越野环境下无人驾驶车辆技术研究综述[J]. 北京理工大学学报，2021，41(11):1137-1144. HU Yuhui，WANG Xu，HU Jiaming，et al. An overview on unmanned vehicle technology in off-road environment[J]. Transactions of Beijing Institute of Technology，2021，41(1):1137-1144.
[3] YOUSIF S. A Study into on-street parking:Effects on traffic congestion[J]. Traffic Engineering and Control，1999，40:424-427.
[4] WIJAYARATNA S. Impacts of on-street parking on road capacity[C]//Australasian Transport Research Forum，2015，21:1-15.
[5] 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). New York:IEEE，2017:1827-1834.
[6] QIN Zhaobo，CHEN Xin，HU Manjiang，et al. A novel path planning methodology for automated valet parking based on directional graph search and geometry curve[J]. Robotics and Autonomous Systems，2020，132:103606.
[7] LI Bai，OUYANG Yakun，LI Xiaohui，et al. Mixed-integer and conditional trajectory planning for an autonomous mining truck in loading/dumping scenarios:A global optimization approach[J]. IEEE Transactions on Intelligent Vehicles，2023，8(2):1512-1522.
[8] LI Bai，FAN Lili，OUYANG Yakun，et al. Online competition of trajectory planning for automated parking:Benchmarks，achievements，learned lessons，and future perspectives[J]. IEEE Transactions on Intelligent Vehicles，2023，8(1):16-21.
[9] 王明强，王震坡，张雷. 基于碰撞风险评估的智能汽车局部路径规划方法研究[J]. 机械工程学报，2021，57(10):28-41. WANG Mingqiang，WANG Zhenpo，ZHANG Lei. Local path planning for intelligent vehicles based on collision risk evaluation[J]. Journal of Mechanical Engineering，2021，57(10):28-41.
[10] 张家旭，王晨，赵健，等. 面向狭小平行泊车位的路径规划与跟踪控制[J]. 吉林大学学报，2021，51(5):1879-1886. ZHANG Jiaxu，WANG Chen，ZHAO Jian. et al. Path planning and tracking control for narrow parallel parking space[J]. Journal of Jilin University 2021，51(5):1879-1886.
[11] 李克强，古谚谌，王永胜，等. 基于预定义几何集的斜列式泊车路径规划方法[J]. 中国公路学报，2021，34(12):1-11. LI Keqiang，GU Yanchen，WANG Yongsheng，et al. Oblique parking path planning method based on predefined geometric set[J]. China Journal of Highway and Transport，2021，34(12):1-11.
[12] 姜武华，辛鑫，陈无畏，等. 基于信息融合的自动泊车系统多工况车位识别和决策规划[J]. 机械工程学报，2021，57(6):131-141. JIANG Wuhua，XIN Xin，CHEN Wuwei，et al. Multi-condition parking space recognition based on information fusion and decision planning of automatic parking system[J]. Journal of Mechanical Engineering，2021，57(6):131-141.
[13] YANG Yi，ZHANG Lu，QU Xin，et al. Smooth path planning for autonomous parking system[C]//2017 IEEE Intelligent Vehicles Symposium (IV). New York:IEEE，2017:167-173.
[14] VOROBIEVA H，GLASER S，MINOIU-ENACHE N，et al. Automatic parallel parking in tiny spots:Path planning and control[J]. IEEE Transactions on Intelligent Transportation Systems，2014，16(1):396-410.
[15] CAI Lei，GUAN Hsin，ZHOU Zhiyao，et al. Parking planning under limited parking corridor space[J]. IEEE Transactions on Intelligent Transportation Systems， 2022，24(2):1962-1981.
[16] DOLGOV D，THRUN S，MONTEMERLO M，et al. Path planning for autonomous vehicles in unknown semi-structured environments[J]. The International Journal of Robotics Research，2010，29(5):485-501.
[17] CHEN Chao，RICKERT M，KNOLL A. Path planning with orientation-aware space exploration guided heuristic search for autonomous parking and maneuvering[C]//2015 IEEE Intelligent Vehicles Symposium (IV). New York:IEEE，2015:1148-1153.
[18] BERGMAN K，LJUNGQVIST O，AXEHILL D. Improved path planning by tightly combining lattice-based path planning and optimal control[J]. IEEE Transactions on Intelligent Vehicles，2020，6(1):57-66.
[19] 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.
[20] HAN Long，DO Q H，MITA S. Unified path planner for parking an autonomous vehicle based on RRT[C]//2011 IEEE International Conference on Robotics and Automation. New York:IEEE，2011:5622-5627.
[21] SUN Zhiru，LEI Boshu，XIE Peijia，et al. Multi-Risk-RRT:An efficient motion planning algorithm for robotic autonomous luggage trolley collection at airports[J/OL]. IEEE Transactions on Intelligent Vehicles:1-13[2024-01-04]. https://ieeexplore.ieee.org/document/10380312.
[22] 钱立军，吴冰，仇多洋，等. 基于hp自适应伪谱法的自主泊车路径规划[J]. 机械工程学报，2020，56(4):125-134. QIAN Lijun，WU Bing，QIU Duoyang，et al. Path planning of autonomous parking based on hp-adaptive pseudospectral method[J]. Journal of Mechanical Engineering，2020，56(4):125-134.
[23] 李柏. 复杂约束下自动驾驶车辆运动规划的计算最优控制方法研究[D]. 杭州:浙江大学，2018. LI Bai. Research on computational optimal control methods for automated vehicle motion planning with complicated constraints[D]. Hangzhou:Zhejiang University，2018.
[24] 余卓平，夏浪，熊璐.自主泊车路径规划一致性方法[J]. 汽车技术，2018，515(8):27-32. YU Zhuoping，XIA Lang，XIONG Lu. A consistency method for autonomous parking path planning[J]. Automobile Technology，2018，515(8):27-32.
[25] YAMAGUCHI T，ISHIGURO T，OKUDA H，et al. Model predictive path planning for autonomous parking based on projected C-Space[C]//2021 IEEE International Intelligent Transportation Systems Conference (ITSC). New York:IEEE，2021:929-935.
[26] 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.
[27] BOYD S，VANDENBERGHE L. Convex optimization[M]. Cambridge:Cambridge University Press，2004.
[28] LI B，ZHANG Y，SHAO Z. Spatio-temporal decomposition:A knowledge-based initialization strategy for parallel parking motion optimization[J]. Knowledge-Based Systems，2016，107:179-196.
[29] ZHANG Xiaojing，LINIGER A，BORRELLI F. Optimization-based collision avoidance[J]. IEEE Transactions on Control Systems Technology，2020，29(3):972-983.
[30] RÖSMANN C，FEITEN W，WÖSCH T，et al. Trajectory modification considering dynamic constraints of autonomous robots[C]//ROBOTIK 2012;7th German Conference on Robotics. VDE，2012:1-6.
[31] LI Bai，ACARMAN T，PENG Xiaoyan，et al. Maneuver planning for automatic parking with safe travel corridors:A numerical optimal control approach[C]//2020 European Control Conference (ECC). New York:IEEE，2020:1993-1998.
[32] LI Bai，ACARMAN T，ZHANG Youmin，et al. Optimization-based trajectory planning for autonomous parking with irregularly placed obstacles:A lightweight iterative framework[J]. IEEE Transactions on Intelligent Transportation Systems，2021，23(8):11970-11981.
[33] 马小陆，梅宏. 基于改进势场蚁群算法的移动机器人全局路径规划[J]. 机械工程学报，2021，57(1):19-27. MA Xiaolu，MEI Hong. Mobile robot global path planning based on improved ant colony system algorithm with potential field[J]. Journal of Mechanical Engineering，2021，57(1):19-27.
[34] LIU Wei，LI Zhiheng，LI Li，et al. Parking like a human:A direct trajectory planning solution[J]. IEEE Transactions on Intelligent Transportation Systems，2017，18(12):3388-3397.
[35] LIN Yilun，LI Li，DAI Xingyuan，et al. Master general parking skill via deep learning[C]//2017 IEEE Intelligent Vehicles Symposium (IV). New York:IEEE，2017:941-946.
[36] CHAI Runqi，LIU Derong，LIU Tianhao，et al. Deep learning-based trajectory planning and control for autonomous ground vehicle parking maneuver[J]. IEEE Transactions on Automation Science and Engineering，2023，20(3):1633-1647.
[37] PADEN B，ČÁP 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.
[38] FETHI D，NEMRA A，LOUADJ K，et al. Simultaneous localization，mapping，and path planning for unmanned vehicle using optimal control[J]. Advances in Mechanical Engineering，2018，10(1):1-25.
[39] POLACK P，ALTCHÉ F，D'ANDRÉA-NOVEL B，et al. The kinematic bicycle model:A consistent model for planning feasible trajectories for autonomous vehicles?[C]//2017 IEEE intelligent vehicles symposium (IV). New York:IEEE，2017:812-818.
[40] GUO Yuqing，GUO Zelin，WANG Yazhou，et al. A survey of trajectory planning methods for autonomous driving — Part I:Unstructured scenarios[J/OL]. IEEE Transactions on Intelligent Vehicles:1-29[2024-01-04]. https://ieeexplore.ieee.org/document/10329446.
[41] LI Bai，ZHANG Youmin. Fast trajectory planning for off-road autonomous driving with a spatiotemporal tunnel and numerical optimal control approach[C]//2019 IEEE 4th International Conference on Advanced Robotics and Mechatronics (ICARM). New York:IEEE，2019:924-929.
[42] BERGMAN K，AXEHILL D. Combining homotopy methods and numerical optimal control to solve motion planning problems[C]//2018 IEEE Intelligent Vehicles Symposium (IV). New York:IEEE，2018:347-354.
[43] LI Bai，LI Li，ACARMAN T，et al. Optimization-based maneuver planning for a tractor-trailer vehicle in a curvy tunnel:A weak reliance on sampling and search[J]. IEEE Robotics and Automation Letters，2021，7(2):706-713
[44] FOURER R，GAY D M，KERNIGHAN B W. AMPL. A modeling language for mathematical programming[J]. Management Science，1990，36(5):519-554.
[45] WÄCHTER A，BIEGLER L T. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming[J]. Mathematical Programming，2006，106:25-57.
[46] HSL. A collection of Fortran codes for large scale scientific computation[EB/OL]. [2023-5-19]. http://www.hsl.rl.ac.uk/.
[47] ZHANG Xiaojing，LINIGER A，SAKAI A，et al. Autonomous parking using optimization-based collision avoidance[C]//2018 IEEE Conference on Decision and Control (CDC). New York:IEEE，2018:4327-4332.