In this paper an analytical and geometry-based path planning method is proposed that provides non-holonomic and collision free paths for parking maneuvers. The proposed method is straightforward in the sense that it does not require any sampling or exploring of the configuration space, or relies on any optimization process. Furthermore, the calculation is fast enough to be used in real-time applications for guiding the vehicle in parking scenarios. For any pair of start-goal configurations, the planner presents an infinite set of solutions. These paths have minimum number of driving direction changes as this can be more important for a driver than the path length. They may have any curvature lower than or equal to the maximum specified curvature. Simulations show the superiority of the method in local path planning over conventional methods such as hybrid A* and optimization based approaches in terms of computation time and path quality attributes such as the number of motion primitives and the number of direction changes. To compose a complete motion planning system, the proposed local planner is applied along with hybrid A* as global planner and a path tracking controller. The performance of the motion planning system is evaluated by simulating a valet parking scenario. MATLAB/Simulink is used to simulate the system, and a comprehensive vehicle model in CARSIM is used to represent the vehicle. Simulation results shows the capability of the proposed motion planner to implement automated valet parking tasks while respecting the physical limitations of the vehicle subsystems and driving comfort requirements.
KatrakazasCQuddusMChenWH, et al. Real-time motion planning methods for autonomous on-road driving: state-of-the-art and future research directions. Transp Res Part C Emerg Technol2015; 60: 416–442.
2.
ClaussmannLRevilloudMGruyerD, et al. A review of motion planning for highway autonomous driving. IEEE Trans Intell Transp Syst2020; 21(5): 1826–1848.
3.
KimJJoKChuK, et al. Road-model-based and graph-structure-based hierarchical path-planning approach for autonomous vehicles. Proc IMechE, Part D: J Auto-mobile Engineering2014; 228(8): 909–928.
YouCLuJFilevD, et al. Advanced planning for autonomous vehicles using reinforcement learning and deep inverse reinforcement learning. Robot Auton Syst2019; 114: 1–18.
6.
LiuCLeeSVarnhagenS, et al. Path planning for autonomous vehicles using model predictive control. In: 2017 IEEE Intelligent Vehicles Symposium (IV), pp.174–179. New York, NY: IEEE. DOI: 10. 1109/IVS.2017.7995716.
7.
RasekhipourYKhajepourAChenSK, et al. A potential field-based model predictive path-planning controller for autonomous road vehicles. IEEE Trans Intell Transp Syst2017; 18(5): 1255–1267.
8.
NakraniNJoshiM. An intelligent fuzzy based hybrid approach for parallel parking in dynamic environment. Procedia Comput Sci2018; 133: 82–91.
9.
WangLGuoLHeY. Path planning algorithm for automatic parallel parking from arbitrary initial angle. In: 2017 10th International symposium on computational intelligence and design (ISCID), 2017, pp.55–58. New York: IEEE. DOI: 10.1109/ISCID.2017.115.
10.
DoQHMitaSYonedaK. A practical and optimal path planning for autonomous parking using fast marching algorithm and support vector machine. IEICE Trans Inf Syst2013; E96.D(12): 2795–2804.
11.
LiBShaoZ. A unified motion planning method for parking an autonomous vehicle in the presence of irregularly placed obstacles. Knowl Based Syst2015; 86: 11–20.
12.
ZipsPBöckMKugiA. Optimisation based path planning for car parking in narrow environments. Robot Auton Syst2016; 79: 1–11.
13.
ZipsPBöckMKugiA. Fast optimization based motion planning and path-tracking control for car parking. IFAC Proc Volumes2013; 46(23): 86–91.
14.
DijkstraEW. A note on two problems in connexion with graphs. Numer Math1959; 1: 269–271.
15.
HartPNilssonNRaphaelB. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern1968; 4(2): 100–107.
16.
DoglovDThrunS. Autonomous driving in semi- structured environments: Mapping and planning. In: 2009 IEEE international conference on robotics and automation, pp.3407–3414. New York: IEEE. DOI: 10.1109/ROBOT.2009.5152682.
17.
DolgovDThrunSMontemerloM, et al. Practical search techniques in path planning for autonomous driving. In: AAAI Workshop - Technical Report, 2008.
18.
DolgovDThrunSMontemerloM, et al. Path planning for autonomous vehicles in unknown semi-structured environments. Int J Rob Res2010; 29(5): 485–501.
19.
MontemerloMBeckerJBhatS, et al. Junior: the Stanford entry in the urban challenge. Berlin, Heidelberg: Springer, 2009. pp.91–123.
20.
PohlI. First results on the effect of error in heuristic search. Mach Intell1970; 5: 219–236.
21.
LavalleSM. Rapidly-exploring random trees: A new tool for path planning. Technical report, 1998.
22.
KuwataYFioreGTeoJ, et al. Motion planning for urban driving using RRT. In: 2008 IEEE/RSJ International conference on intelligent robots and systems, Nice, France, 22–26 September, pp.1681–1686. New York, NY: IEEE. DOI: 10.1109/IROS.2008. 4651075.
23.
KaramanSFrazzoliE. Optimal kinodynamic motion planning using incremental sampling-based methods. In: 49th IEEE conference on decision and control (CDC), pp.7681–7687. New York, NY: IEEE. DOI: 10.1109/CDC.2010.5717430.
24.
NoreenIKhanAHabibZ. Optimal path planning using RRT* based approaches: A survey and future directions. Int J Adv Comput Sci Appl2016; 7: 7.
25.
WangYJhaDKAkemiY. A two-stage RRT path planner for automated parking. In: 2017 13th IEEE conference on automation science and engineering (CASE), pp.496–502. DOI: 10.1109/COASE.2017.8256153.
26.
ZhangBLiZNiY, et al. Research on path planning and tracking control of automatic parking system. World Electr Veh J2022; 13: 14.
27.
ZhdanovAAKlimovDMKorolevVV, et al. Modeling parallel parking a car. J Comput Syst Sci Int2008; 47: 907–917.
28.
ChoiSBoussardCd’Andréa-NovelB. Easy path planning and robust control for automatic parallel parking. IFAC Proc Volumes2011; 44(1): 656–661.
29.
VorobievaHGlaserSMinoiu-EnacheN, et al. Geometric path planning for automatic parallel parking in tiny spots. IFAC Proceedings Volumes 20122012; 45(24): 36–42.
30.
PadenBCapMYongSZ, et al. A survey of motion planning and control techniques for self-driving urban vehicles. IEEE Trans Intell Vehicles2016; 1(1): 33–55.
31.
ReedsJSheppL. Optimal paths for a car that goes both forwards and backwards. Pac J Math1990; 145: 367–393.
32.
DubinsLE. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. Am J Math1957; 79(3): 497–516.
33.
FraichardTScheuerA. From Reeds and Shepp’s to continuous-curvature paths. IEEE Trans Robot2004; 20(6): 1025–1035.
34.
KissDTeveszG. Autonomous path planning for road vehicles in narrow environments: an efficient continuous curvature approach. J Adv Transport2017; 2017(2): 1–27.
35.
KissDPappD. Effective navigation in narrow areas: A planning method for autonomous cars. In: 2017 IEEE 15th international symposium on applied machine intelligence and informatics (SAMI), pp.000423–000430. New York, NY: IEEE. DOI: 10.1109/SAMI. 2017.7880346.
36.
Gómez-BravoFCuestaFOlleroA, et al. Continuous curvature path generation based on -spline curves for parking manoeuvres. Robot Auton Syst2008; 56: 360–372.
37.
MaekawaTNodaTTamuraS, et al. Curvature continuous path generation for autonomous vehicle using b-spline curves. Comput Des2010; 42(4): 350–359.
38.
GeSSLaiXCAl MamunA. Sensor-based path planning for nonholonomic mobile robots subject to dynamic constraints. Robot Auton Syst2007; 55(7): 513–526.
39.
PerezJGodoyJVillagraJ, et al. Trajectory generator for autonomous vehicles in urban environments. In: 2013 IEEE International conference on robotics and automation, pp.409–414. New York, NY: IEEE. DOI:10.1109/ICRA.2013.6630608.
40.
RavankarARavankarAAKobayashiY, et al. Path smoothing techniques in robot navigation: state-of-the-art, current and future challenges. Sensors2018; 18(9): 3170.
41.
RavankarARavankarAAKobayashiY, et al. SHP: smooth hypocycloidal paths with collision-free and decoupled multi-robot path planning. Int J Adv Robot Syst2016; 13(3): 133.
42.
EspostoFGoosJTeerhuisA, et al. Hybrid path planning for non-holonomic autonomous vehicles: An experimental evaluation. In: 2017 5th IEEE international conference on models and technologies for intelligent transportation systems (MT-ITS). pp. 25–30. New York: IEEE. DOI: 10.1109/MTITS.2017. 8005682.
43.
QinZChenXHuM, et al. A novel path planning methodology for automated valet parking based on directional graph search and geometry curve. Robot Auton Syst2020; 132: 103606.
44.
BadshahIM. Automated docking of a scaled tractor semi-trailer. Master’s Thesis, Eindhoven University of Technology, The Netherlands, 2018.
45.
KuralK. Analysis of high capacity vehicles for Europe: application of performance based standards and improving maneuverability. PhD Thesis, Eindhoven University of Technology, The Netherlands, 2019.
46.
SchmeitzAZegersJPloegJ, et al. Towards a generic lateral control concept for cooperative automated driving theoretical and experimental evaluation. In: 2017 5th IEEE international conference on models and technologies for intelligent transportation systems (MT-ITS), pp.134–139. New York, NY: IEEE. DOI: 10.1109/MTITS.2017.8005653.
47.
WächterABieglerLT. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math Program2006; 106(1): 25–57.
48.
CizniarMSalhiDFikarM, et al. A matlab pack-age for orthogonal collocations on finite elements in dynamic optimisation. In: 15th Int. Conference of Process Control, 2005, https://www.uiam.sk/assets/publication_info.php?id_pub=227 (accessed 25 December 2021).
49.
WangSYuQZhaoX. Study on driver’s turning intention recognition hybrid model of GHMM and GGAP-RBF neural network. Adv Mech Eng2018; 10: 168781401876498.
50.
LuptácikM. Mathematical optimization and economic analysis. Springer Optimization and Its Applications. New York, NY: Springer, 2010.
