{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T23:42:12Z","timestamp":1771026132805,"version":"3.50.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,11,12]],"date-time":"2019-11-12T00:00:00Z","timestamp":1573516800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,11,12]],"date-time":"2019-11-12T00:00:00Z","timestamp":1573516800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["51327801"],"award-info":[{"award-number":["51327801"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Intell Robot Appl"],"published-print":{"date-parts":[[2019,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n<jats:p>In this paper, we present a bilevel optimal motion planning (BOMP) model for autonomous parking. The BOMP model treats motion planning as an optimal control problem, in which the upper level is designed for vehicle nonlinear dynamics, and the lower level is for geometry collision-free constraints. The significant feature of the BOMP model is that the lower level is a linear programming problem that serves as a constraint for the upper-level problem. That is, an optimal control problem contains an embedded optimization problem as constraints. Traditional optimal control methods cannot solve the BOMP problem directly. Therefore, the modified approximate Karush\u2013Kuhn\u2013Tucker theory is applied to generate a general nonlinear optimal control problem. Then the pseudospectral optimal control method solves the converted problem. Particularly, the lower level is the <jats:inline-formula><jats:alternatives><jats:tex-math>$$J_2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>J<\/mml:mi><mml:mn>2<\/mml:mn><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-function that acts as a distance function between convex polyhedron objects. Polyhedrons can approximate objects in higher precision than spheres or ellipsoids. As a result, a fast high-precision BOMP algorithm for autonomous parking concerning dynamical feasibility and collision-free property is proposed. Simulation results and experiment on Turtlebot3 validate the BOMP model, and demonstrate that the computation speed increases almost two orders of magnitude compared with the area criterion based collision avoidance method.<\/jats:p>","DOI":"10.1007\/s41315-019-00109-z","type":"journal-article","created":{"date-parts":[[2019,11,12]],"date-time":"2019-11-12T19:03:03Z","timestamp":1573585383000},"page":"370-382","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["A bilevel optimal motion planning (BOMP) model with application to autonomous parking"],"prefix":"10.1007","volume":"3","author":[{"given":"Shenglei","family":"Shi","sequence":"first","affiliation":[]},{"given":"Youlun","family":"Xiong","sequence":"additional","affiliation":[]},{"given":"Jiankui","family":"Chen","sequence":"additional","affiliation":[]},{"given":"Caihua","family":"Xiong","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,11,12]]},"reference":[{"issue":"1","key":"109_CR1","doi-asserted-by":"publisher","first-page":"105","DOI":"10.3934\/naco.2012.2.105","volume":"2","author":"S Albrecht","year":"2012","unstructured":"Albrecht, S., Leibold, M., Ulbrich, M.: A bilevel optimization approach to obtain optimal cost functions for human arm movements. Numer. Algebra Control Optim. 2(1), 105\u2013127 (2012)","journal-title":"Numer. Algebra Control Optim."},{"issue":"1","key":"109_CR2","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/15M1015984","volume":"26","author":"F Benita","year":"2016","unstructured":"Benita, F., Mehlitz, P.: Bilevel optimal control with final-state-dependent finite-dimensional lower level. SIAM J. Optim. 26(1), 718\u2013752 (2016)","journal-title":"SIAM J. Optim."},{"key":"109_CR3","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718577","volume-title":"Practical Methods for Optimal Control and Estimation Using Nonlinear Programming","author":"JT Betts","year":"2010","unstructured":"Betts, J.T.: Practical Methods for Optimal Control and Estimation Using Nonlinear Programming, vol. 19. Siam, Al Burhama (2010)"},{"key":"109_CR4","doi-asserted-by":"publisher","DOI":"10.1201\/9781315137667","volume-title":"Applied Optimal Control: Optimization, Estimation and Control","author":"AE Bryson","year":"2018","unstructured":"Bryson, A.E.: Applied Optimal Control: Optimization, Estimation and Control. Routledge, Abingdon (2018)"},{"issue":"5","key":"109_CR5","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1177\/0278364909359210","volume":"29","author":"D Dolgov","year":"2010","unstructured":"Dolgov, D., Thrun, S., Montemerlo, M., Diebel, J.: Path planning for autonomous vehicles in unknown semi-structured environments. Int. J. Robot. Res. 29(5), 485\u2013501 (2010)","journal-title":"Int. J. Robot. Res."},{"issue":"3","key":"109_CR6","doi-asserted-by":"publisher","first-page":"1225","DOI":"10.1109\/TITS.2014.2354423","volume":"16","author":"X Du","year":"2015","unstructured":"Du, X., Tan, K.K.: Autonomous reverse parking system based on robust path generation and improved sliding mode control. IEEE Trans. Intell. Transp. Syst. 16(3), 1225\u20131237 (2015)","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"issue":"3","key":"109_CR7","doi-asserted-by":"publisher","first-page":"497","DOI":"10.2307\/2372560","volume":"79","author":"LE Dubins","year":"1957","unstructured":"Dubins, L.E.: On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. Am. J. Math. 79(3), 497\u2013516 (1957)","journal-title":"Am. J. Math."},{"issue":"4","key":"109_CR8","doi-asserted-by":"publisher","first-page":"1463","DOI":"10.1007\/s10898-012-9920-5","volume":"56","author":"J Dutta","year":"2013","unstructured":"Dutta, J., Deb, K., Tulshyan, R., Arora, R.: Approximate kkt points and a proximity measure for termination. J. Glob. Optim. 56(4), 1463\u20131499 (2013)","journal-title":"J. Glob. Optim."},{"issue":"4","key":"109_CR9","doi-asserted-by":"publisher","first-page":"1135","DOI":"10.1109\/TITS.2015.2498841","volume":"17","author":"D Gonz\u00e1lez","year":"2016","unstructured":"Gonz\u00e1lez, D., P\u00e9rez, J., Milan\u00e9s, V., Nashashibi, F.: A review of motion planning techniques for automated vehicles. IEEE Trans. Intell. Transp. Syst. 17(4), 1135\u20131145 (2016)","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"issue":"5","key":"109_CR10","doi-asserted-by":"publisher","first-page":"954","DOI":"10.1109\/TRO.2010.2062090","volume":"26","author":"M Haddad","year":"2010","unstructured":"Haddad, M., Khalil, W., Lehtihet, H.: Trajectory planning of unicycle mobile robots with a trapezoidal-velocity constraint. IEEE Trans. Robot. 26(5), 954\u2013962 (2010)","journal-title":"IEEE Trans. Robot."},{"issue":"5","key":"109_CR11","doi-asserted-by":"publisher","first-page":"1194","DOI":"10.1137\/0913069","volume":"13","author":"P Hansen","year":"1992","unstructured":"Hansen, P., Jaumard, B., Savard, G.: New branch-and-bound rules for linear bilevel programming. SIAM J. Sci. Comput. 13(5), 1194\u20131217 (1992)","journal-title":"SIAM J. Sci. Comput."},{"issue":"3","key":"109_CR12","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1177\/027836498600500304","volume":"5","author":"K Kant","year":"1986","unstructured":"Kant, K., Zucker, S.W.: Toward efficient trajectory planning: the path-velocity decomposition. Int. J. Robot. Res. 5(3), 72\u201389 (1986)","journal-title":"Int. J. Robot. Res."},{"issue":"1","key":"109_CR13","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1177\/027836498600500106","volume":"5","author":"O Khatib","year":"1986","unstructured":"Khatib, O.: Real-time obstacle avoidance for manipulators and mobile robots. Int. J. Robot. Res. 5(1), 90\u201398 (1986)","journal-title":"Int. J. Robot. Res."},{"key":"109_CR14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877","volume-title":"Planning Algorithms","author":"SM LaValle","year":"2006","unstructured":"LaValle, S.M.: Planning Algorithms. Cambridge University Press, Cambridge (2006)"},{"key":"109_CR15","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.knosys.2015.04.016","volume":"86","author":"B Li","year":"2015","unstructured":"Li, B., Shao, Z.: A unified motion planning method for parking an autonomous vehicle in the presence of irregularly placed obstacles. Knowl. Based Syst. 86, 11\u201320 (2015)","journal-title":"Knowl. Based Syst."},{"issue":"11","key":"109_CR16","doi-asserted-by":"publisher","first-page":"3263","DOI":"10.1109\/TITS.2016.2546386","volume":"17","author":"B Li","year":"2016","unstructured":"Li, B., Wang, K., Shao, Z.: Time-optimal maneuver planning in automatic parallel parking using a simultaneous dynamic optimization approach. IEEE Trans. Intell. Transp. Syst. 17(11), 3263\u20133274 (2016)","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"issue":"8","key":"109_CR17","doi-asserted-by":"publisher","first-page":"933","DOI":"10.1177\/0278364909340445","volume":"28","author":"M Likhachev","year":"2009","unstructured":"Likhachev, M., Ferguson, D.: Planning long dynamically feasible maneuvers for autonomous vehicles. Int. J. Robot. Res. 28(8), 933\u2013945 (2009)","journal-title":"Int. J. Robot. Res."},{"issue":"12","key":"109_CR18","doi-asserted-by":"publisher","first-page":"3388","DOI":"10.1109\/TITS.2017.2687047","volume":"18","author":"W Liu","year":"2017","unstructured":"Liu, W., Li, Z., Li, L., Wang, F.Y.: Parking like a human: a direct trajectory planning solution. IEEE Transactions on Intelligent Transportation Systems 18(12), 3388\u20133397 (2017)","journal-title":"IEEE Transactions on Intelligent Transportation Systems"},{"key":"109_CR19","doi-asserted-by":"crossref","unstructured":"Mamou, K., Ghorbel, F.: A simple and efficient approach for 3d mesh approximate convex decomposition. In: Proceedings of IEEE International Conference Image Processing (ICIP), IEEE, pp. 3501\u20133504 (2009)","DOI":"10.1109\/ICIP.2009.5414068"},{"issue":"3","key":"109_CR20","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1109\/TCST.2006.890289","volume":"15","author":"B Muller","year":"2007","unstructured":"Muller, B., Deutscher, J., Grodde, S.: Continuous curvature trajectory design and feedforward control for parking a car. IEEE Trans. Control Syst. Technol. 15(3), 541\u2013553 (2007)","journal-title":"IEEE Trans. Control Syst. Technol."},{"issue":"5","key":"109_CR21","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1109\/TITS.2016.2597966","volume":"18","author":"J Nilsson","year":"2016","unstructured":"Nilsson, J., Br\u00e4nnstr\u00f6m, M., Coelingh, E., Fredriksson, J.: Lane change maneuvers for automated vehicles. IEEE Trans. Intell. Transp. Syst. 18(5), 1087\u20131096 (2016)","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"issue":"3","key":"109_CR22","doi-asserted-by":"publisher","first-page":"1106","DOI":"10.1109\/TVT.2008.928643","volume":"58","author":"MB Oetiker","year":"2009","unstructured":"Oetiker, M.B., Baker, G.P., Guzzella, L.: A navigation-field-based semi-autonomous nonholonomic vehicle-parking assistant. IEEE Trans. Veh. Technol. 58(3), 1106\u20131118 (2009)","journal-title":"IEEE Trans. Veh. Technol."},{"issue":"5","key":"109_CR23","doi-asserted-by":"publisher","first-page":"1255","DOI":"10.1109\/TITS.2016.2604240","volume":"18","author":"Y Rasekhipour","year":"2016","unstructured":"Rasekhipour, Y., Khajepour, A., Chen, S.K., Litkouhi, B.: A potential field-based model predictive path-planning controller for autonomous road vehicles. IEEE Trans. Intell. Transp. Syst. 18(5), 1255\u20131267 (2016)","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"issue":"2","key":"109_CR24","doi-asserted-by":"publisher","first-page":"367","DOI":"10.2140\/pjm.1990.145.367","volume":"145","author":"J Reeds","year":"1990","unstructured":"Reeds, J., Shepp, L.: Optimal paths for a car that goes both forwards and backwards. Pac. J. Math. 145(2), 367\u2013393 (1990)","journal-title":"Pac. J. Math."},{"issue":"2","key":"109_CR25","doi-asserted-by":"publisher","first-page":"1215","DOI":"10.1109\/LRA.2018.2794582","volume":"3","author":"DR Robinson","year":"2018","unstructured":"Robinson, D.R., Mar, R.T., Estabridis, K., Hewer, G.: An efficient algorithm for optimal trajectory generation for heterogeneous multi-agent systems in non-convex environments. IEEE Robot. Autom. Lett. 3(2), 1215\u20131222 (2018)","journal-title":"IEEE Robot. Autom. Lett."},{"issue":"2","key":"109_CR26","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/j.arcontrol.2012.09.002","volume":"36","author":"IM Ross","year":"2012","unstructured":"Ross, I.M., Karpenko, M.: A review of pseudospectral optimal control: from theory to flight. Annu. Rev. Control 36(2), 182\u2013197 (2012)","journal-title":"Annu. Rev. Control"},{"issue":"2","key":"109_CR27","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.ejor.2016.08.027","volume":"257","author":"A Sinha","year":"2017","unstructured":"Sinha, A., Malo, P., Deb, K.: Evolutionary algorithm for bilevel optimization using approximations of the lower level optimal solution mapping. Eur. J. Oper. Res. 257(2), 395\u2013411 (2017)","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"109_CR28","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1109\/TEVC.2017.2712906","volume":"22","author":"A Sinha","year":"2018","unstructured":"Sinha, A., Malo, P., Deb, K.: A review on bilevel optimization: from classical to evolutionary approaches and applications. IEEE Trans. Evolut. Comput. 22(2), 276\u2013295 (2018)","journal-title":"IEEE Trans. Evolut. Comput."},{"issue":"4","key":"109_CR29","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1109\/TIV.2017.2769882","volume":"2","author":"Y Tazaki","year":"2017","unstructured":"Tazaki, Y., Okuda, H., Suzuki, T.: Parking trajectory planning using multiresolution state roadmaps. IEEE Trans. Intell. Veh. 2(4), 298\u2013307 (2017)","journal-title":"IEEE Trans. Intell. Veh."},{"issue":"2","key":"109_CR30","doi-asserted-by":"publisher","first-page":"1268","DOI":"10.1109\/LRA.2018.2795655","volume":"3","author":"S Upadhyay","year":"2018","unstructured":"Upadhyay, S., Ratnoo, A.: A point-to-ray framework for generating smooth parallel parking maneuvers. IEEE Robot. Autom. Lett. 3(2), 1268\u20131275 (2018)","journal-title":"IEEE Robot. Autom. Lett."},{"issue":"2","key":"109_CR31","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/BF02191670","volume":"81","author":"L Vicente","year":"1994","unstructured":"Vicente, L., Savard, G., J\u00fadice, J.: Descent approaches for quadratic bilevel programming. J. Optim. Theory Appl. 81(2), 379\u2013399 (1994)","journal-title":"J. Optim. Theory Appl."},{"issue":"1","key":"109_CR32","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1109\/TITS.2014.2335054","volume":"16","author":"H Vorobieva","year":"2015","unstructured":"Vorobieva, H., Glaser, S., Minoiu-Enache, N., Mammar, S.: Automatic parallel parking in tiny spots: path planning and control. IEEE Trans. Intell. Transp. Syst. 16(1), 396\u2013410 (2015)","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"issue":"1","key":"109_CR33","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s10107-004-0559-y","volume":"106","author":"A W\u00e4chter","year":"2006","unstructured":"W\u00e4chter, A., Biegler, L.T.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program 106(1), 25\u201357 (2006)","journal-title":"Math. Program"},{"issue":"2","key":"109_CR34","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1109\/TRO.2009.2015610","volume":"25","author":"H Wang","year":"2009","unstructured":"Wang, H., Chen, Y., Sou\u00e8res, P.: A geometric algorithm to compute time-optimal trajectories for a bidirectional steered robot. IEEE Trans. Robot. 25(2), 399\u2013413 (2009)","journal-title":"IEEE Trans. Robot."},{"key":"109_CR35","first-page":"7","volume-title":"Numerical optimization","author":"S Wright","year":"1999","unstructured":"Wright, S., Nocedal, J.: Numerical optimization, vol. 35(67\u201368), p. 7. Springer Science, New York (1999)"},{"issue":"2","key":"109_CR36","first-page":"1","volume":"8","author":"Y Xiong","year":"1987","unstructured":"Xiong, Y.: Generalized criterion for minimum zone and computer arbitrament. Acta Metrol. Sin. 8(2), 1\u20138 (1987)","journal-title":"Acta Metrol. Sin."},{"issue":"2","key":"109_CR37","first-page":"75","volume":"4","author":"Y Xiong","year":"1989","unstructured":"Xiong, Y., Ding, H.: General criterion and control strategy of collision-free movement for manipulators. Int. J. Robot. Autom. 4(2), 75\u201380 (1989)","journal-title":"Int. J. Robot. Autom."},{"issue":"1","key":"109_CR38","doi-asserted-by":"publisher","first-page":"834","DOI":"10.1109\/TIE.2017.2739680","volume":"65","author":"D Xu","year":"2018","unstructured":"Xu, D., Shi, Y., Ji, Z.: Model-free adaptive discrete-time integral sliding-mode-constrained-control for autonomous 4wmv parking systems. IEEE Trans. Ind. Electron. 65(1), 834\u2013843 (2018)","journal-title":"IEEE Trans. Ind. Electron."},{"key":"109_CR39","first-page":"1","volume":"99","author":"Z Ye","year":"2018","unstructured":"Ye, Z., Li, K., Stapelbroek, M., Savelsberg, R., G\u00fcnther, M., Pischinger, S.: Variable step-size discrete dynamic programming for vehicle speed trajectory optimization. IEEE Trans. Intell. Transp. Syst. 99, 1\u20139 (2018)","journal-title":"IEEE Trans. Intell. Transp. Syst."},{"key":"109_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.robot.2016.02.004","volume":"79","author":"P Zips","year":"2016","unstructured":"Zips, P., B\u00f6ck, M., Kugi, A.: Optimisation based path planning for car parking in narrow environments. Robot. Auton. Syst. 79, 1\u201311 (2016)","journal-title":"Robot. Auton. Syst."}],"container-title":["International Journal of Intelligent Robotics and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41315-019-00109-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s41315-019-00109-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s41315-019-00109-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,11]],"date-time":"2020-11-11T01:17:30Z","timestamp":1605057450000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s41315-019-00109-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,12]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["109"],"URL":"https:\/\/doi.org\/10.1007\/s41315-019-00109-z","relation":{},"ISSN":["2366-5971","2366-598X"],"issn-type":[{"value":"2366-5971","type":"print"},{"value":"2366-598X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,12]]},"assertion":[{"value":"22 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 October 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 November 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}