Geodesic
Path Planning Followed by Kinodynamic Smoothing
Russian journal of nonlinear dynamics, Tome 17 (2021) no. 4, pp. 491-505.

Voir la notice de l'article provenant de la source Math-Net.Ru

Any obstacle-free path planning algorithm, in general, gives a sequence of waypoints that connect start and goal positions by a sequence of straight lines, which does not ensure the smoothness and the dynamic feasibility to maneuver the MAV. Kinodynamic-based motion planning is one of the ways to impose dynamic feasibility in planning. However, kinodynamic motion planning is not an optimal solution due to high computational demands for real-time applications. Thus, we explore path planning followed by kinodynamic smoothing while ensuring the dynamic feasibility of MAV. The main difference in the proposed technique is not to use kinodynamic planning when finding a feasible path, but rather to apply kinodynamic smoothing along the obtained feasible path. We have chosen a geometric-based path planning algorithm “RRT*” as the path finding algorithm. In the proposed technique, we modified the original RRT* introducing an adaptive search space and a steering function that helps to increase the consistency of the planner. Moreover, we propose a multiple RRT* that generates a set of desired paths. The optimal path from the generated paths is selected based on a cost function. Afterwards, we apply kinodynamic smoothing that will result in a dynamically feasible as well as obstacle-free path. Thereafter, a b-spline-based trajectory is generated to maneuver the vehicle autonomously in unknown environments. Finally, we have tested the proposed technique in various simulated environments. According to the experiment results, we were able to speed up the path planning task by 1.3 times when using the proposed multiple RRT* over the original RRT*.
Keywords: RRT*, B-spline, ellipsoidal search space.
Mots-clés : iLQR, OctoMap 
@article{ND_2021_17_4_a9,
     author = {G. Kulathunga and D. Devitt and R. Fedorenko and A. S. Klimchik},
     title = {Path {Planning} {Followed} by {Kinodynamic} {Smoothing}},
     journal = {Russian journal of nonlinear dynamics},
     pages = {491--505},
     publisher = {mathdoc},
     volume = {17},
     number = {4},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ND_2021_17_4_a9/}
}
TY  - JOUR
AU  - G. Kulathunga
AU  - D. Devitt
AU  - R. Fedorenko
AU  - A. S. Klimchik
TI  - Path Planning Followed by Kinodynamic Smoothing
JO  - Russian journal of nonlinear dynamics
PY  - 2021
SP  - 491
EP  - 505
VL  - 17
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ND_2021_17_4_a9/
LA  - en
ID  - ND_2021_17_4_a9
ER  - 
%0 Journal Article
%A G. Kulathunga
%A D. Devitt
%A R. Fedorenko
%A A. S. Klimchik
%T Path Planning Followed by Kinodynamic Smoothing
%J Russian journal of nonlinear dynamics
%D 2021
%P 491-505
%V 17
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ND_2021_17_4_a9/
%G en
%F ND_2021_17_4_a9
G. Kulathunga; D. Devitt; R. Fedorenko; A. S. Klimchik. Path Planning Followed by Kinodynamic Smoothing. Russian journal of nonlinear dynamics, Tome 17 (2021) no. 4, pp. 491-505. http://geodesic.mathdoc.fr/item/ND_2021_17_4_a9/

[1] Karaman, S. and Frazzoli, E., “Sampling-Based Algorithms for Optimal Motion Planning”, Int. J. Robot. Res., 30:7 (2011), 846–894 | DOI

[2] Hornung, A., Wurm, K. M., Bennewitz, M., Stachniss, C., and Burgard, W., “OctoMap: An Efficient Probabilistic 3D Mapping Framework Based on Octrees”, Auton. Robot., 34:3 (2013), 189–206 | DOI

[3] Steinbrücker, F., Sturm, J., and Cremers, D., “Volumetric 3D Mapping in Real-Time on a CPU”, IEEE Internat. Conf. on Robotics and Automation (ICRA'2014), 2021–2028

[4] Nießner, M., Zollhöfer, M., Shahram, I., and Stamminger, M., “Real-Time 3D Reconstruction at Scale Using Voxel Hashing”, ACM Trans. Graph., 32:6 (2013), 169, 11 pp.

[5] Oleynikova, H., Taylor, Z., Fehr, M., Nieto, J., and Siegwart, R., Voxblox: Building 3D Signed Distance Fields for Planning, 2016, 8 pp., arXiv: 1611.03631 [cs.RO]

[6] Souissi, O., Benatitallah, R., Duvivier, D., Artiba, A., Belanger, N., and Feyzeau, P., “Path Planning: A 2013 Survey”, Proc. of the 2013 Internat. Conf. on Industrial Engineering and Systems Management (IESM), 8 pp.

[7] Kavraki, L. E., Svestka, P., Latombe, J.-C., and Overmars, M. H., “Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces”, IEEE Trans. Rob. Autom., 12:4 (1996), 566–580 | DOI

[8] LaValle, S. M., Rapidly-Exploring Random Trees: A New Tool for Path Planning, Iowa State Univ. Technical Report 11, 1998, 4 pp.

[9] Donald, B., Xavier, P., Canny, J., and Reif, J., “Kinodynamic Motion Planning”, J. ACM, 40:5 (1993), 1048–1066 | DOI | MR | Zbl

[10] Lan, M., Lai, Sh., Bi, Y., Qin, H., Li, J., Lin, F., and Chen, B. M., “BIT*-Based Path Planning for Micro Aerial Vehicles”, IECON 2016: Proc. of the 42nd Annual Conf. of the IEEE Industrial Electronics Society, 6079–6084

[11] Starek, J. A., Gomez, J. V., Schmerling, E., Janson, L., Moreno, L., and Pavone, M., “An Asymptotically-Optimal Sampling-Based Algorithm for Bi-Directional Motion Planning”, IEEE/RSJ Internat. Conf. on Intelligent Robots and Systems (IROS'2015), 2072–2078

[12] LaValle, S. M. and Kuffner, J. J., Jr., “Randomized Kinodynamic Planning”, Int. J. Robot. Res., 20:5 (2001), 378–400 | DOI

[13] Perez, A., Platt, R., Konidaris, G., Kaelbling, L., and Lozano-Perez, T., “LQR-RRT*: Optimal Sampling-Based Motion Planning with Automatically Derived Extension Heuristics”, 2012 IEEE Internat. Conf. on Robotics and Automation, 2537–2542

[14] Glassman, E. and Tedrake, R., “A Quadratic Regulator-Based Heuristic for Rapidly Exploring State Space”, 2010 IEEE Internat. Conf. on Robotics and Automation, 5021–5028

[15] van den Berg, J., “Extended LQR: Locally-Optimal Feedback Control for Systems with Non-Linear Dynamics and Non-Quadratic Cost”, Robotics Research, Springer Tracts Adv. Robot., 114, eds. M. Inaba, P. Corke, Springer, Cham, 2016, 39–56 | DOI

[16] Zhu, Zh., Schmerling, E., and Pavone, M., “A Convex Optimization Approach to Smooth Trajectories for Motion Planning with Car-Like Robots”, Proc. of the 54th IEEE Conf. on Decision and Control (CDC'2015), 835–842

[17] Rösmann, Ch., Hoffmann, F., and Bertram, T., “Kinodynamic Trajectory Optimization and Control for Car-Like Robots”, IEEE/RSJ Internat. Conf. on Intelligent Robots and Systems (IROS'2017), 5681–5686

[18] Zhou, B., Gao, F., Wang, L., Liu, Ch., and Shen, Sh., “Robust and Efficient Quadrotor Trajectory Generation for Fast Autonomous Flight”, IEEE Robot. Autom. Lett., 4:4 (2019), 3529–3536 | DOI

[19] Biagiotti, L. and Melchiorri, C., Trajectory Planning for Automatic Machines and Robots, Springer, Berlin, 2008, 528 pp.

[20] Mueller, M. W., Hehn, M., and D'Andrea, R., “A Computationally Efficient Algorithm for State-to-State Quadrocopter Trajectory Generation and Feasibility Verification”, 2013 IEEE/RSJ Internat. Conf. on Intelligent Robots and Systems, 3480–3486

[21] Paranjape, A. A., Meier, K. C., Shi, X., Chung, S.-J., and Hutchinson, S., “Motion Primitives and 3D Path Planning for Fast Flight through a Forest”, Int. J. Robot. Res., 34:3 (2015), 357–377 | DOI

[22] Zucker, M., Ratliff, N., Dragan, A. D., Pivtoraiko, M., Klingensmith, M., Dellin, Ch. M., Bagnell, J. A., and Srinivasa, S. S., “Chomp: Covariant Hamiltonian Optimization for Motion Planning”, Int. J. Robot. Res., 32:9–10 (2013), 1164–1193 | DOI

[23] Oleynikova, H., Burri, M., Taylor, Z., Nieto, J., Siegwart, R., and Galceran, E., “Continuous-Time Trajectory Optimization for Online UAV Replanning”, IEEE/RSJ Internat. Conf. on Intelligent Robots and Systems (IROS'2016), 5332–5339

[24] Usenko, V., von Stumberg, L., Pangercic, A., and Cremers, D., “Real-Time Trajectory Replanning for MAVs Using Uniform B-Splines and a 3D Circular Buffer”, IEEE/RSJ Internat. Conf. on Intelligent Robots and Systems (IROS'2017), 215–222

[25] Mellinger, D. and Kumar, V., “Minimum Snap Trajectory Generation and Control for Quadrotors”, 2011 IEEE Internat. Conf. on Robotics and Automation, 2520–2525

[26] Hoffmann, G., Waslander, S., and Tomlin, C., “Quadrotor Helicopter Trajectory Tracking Control”, AIAA Guidance, Navigation and Control Conference and Exhibit (Honolulu, Hawaii, 2008), AIAA 2008-7410, 14 pp.

[27] Babaei, A. and Karimi, A., Optimal Trajectory-Planning of UAVs via B-Splines and Disjunctive Programming, 2018, 12 pp., arXiv: 1807.02931 [math.OC]

[28] Biagiotti, L. and Melchiorri, C., “B-Spline Based Filters for Multi-Point Trajectories Planning”, 2010 IEEE Internat. Conf. on Robotics and Automation, 3065–3070

[29] Bobrow, J. E., “Optimal Robot Plant Planning Using the Minimum-Time Criterion”, IEEE J. Robot. Autom., 4:4 (1988), 443–450 | DOI

[30] Wang, C.-H. and Horng, J.-G., “Constrained Minimum-Time Path Planning for Robot Manipulators via Virtual Knots of the Cubic B-Spline Functions”, IEEE Trans. Automat. Control, 35:5 (1990), 573–577 | DOI | Zbl

[31] Guttman, A., “R-Trees: A Dynamic Index Structure for Spatial Searching”, Proc. of the 1984 ACM SIGMOD Internat. Conf. on Management of Data, 47–57

[32] Kulathunga, G, Fedorenko, R., Kopylov, S., and Klimchik, A., Real-Time Long Range Trajectory Replanning for MAVs in the Presence of Dynamic Obstacles, 2020, 9 pp., arXiv: 2001.03605 [cs.RO]

[33] van den Berg, J., “Iterated LQR Smoothing for Locally-Optimal Feedback Control of Systems with Non-Linear Dynamics and Non-Quadratic Cost”, American Control Conference (Portland, OR, USA, June 2014), 1912–1918

[34] The Riccati Equation, eds. S. Bittanti, A. J. Laub, J. C. Willems, Springer, Berlin, 2012, 352 pp. | MR