Abstract
In this work we study a navigation problem for a nonholonomic differential drive robot operating in the environment with static and dynamic obstacles. We present a multi-phase approach to solve it, which is based on heuristic search to tackle the trajectory planning problem and specific methods of the control theory to solve the path following problem. Results of the experimental evaluation show that the suggested controller is one order of magnitude faster than the widely used in robotics Model-Predictive Control (MPC) and is capable of accurately following the reference trajectory. On the planning side we show that the suggested planner is scalable and is able to plan in reasonable time.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
REFERENCES
McGuire, K.N., de Croon, G.C.H.E., and Tuyls, K.A., Comparative study of bug algorithms for robot navigation, Rob. Auton. Syst., 2019, vol. 121, p. 103261.
Berg, J. et al., Reciprocal \( n \)-body collision avoidance, in Robotics Research, Berlin–Heidelberg: Springer, 2011, pp. 3–19.
Koenig, S. and Likhachev, M., D* Lite, 18th Natl. Conf. Artif. Intell., 2002„ pp. 476–483.
Phillips, M. and Likhachev, M., SIPP: safe interval path planning for dynamic environments, 2011 IEEE Int. Conf. Rob. Autom., IEEE, 2011, pp. 5628–5635.
Mayne, D.Q. et al., Constrained model predictive control: stability and optimality, Automatica, 2000, vol. 36, no. 6, pp. 789–814.
Bocharov, A.V. and Verbovetskii, A.M., Simmetrii i zakony sokhraneniya matematicheskoi fiziki (Symmetries and Conservation Laws of Mathematical Physics), Moscow: Faktorial, 2005.
Likhachev, M. and Ferguson, D., Planning long dynamically feasible maneuvers for autonomous vehicles, Int. J. Rob. Res., 2009, vol. 28, no. 8, pp. 933–945.
Sakcak, B. et al., Sampling-based optimal kinodynamic planning with motion primitives, Auton. Rob., 2019, vol. 43, no. 7, pp. 1715–1732.
Pivtoraiko, M. and Kelly, A., Generating near minimal spanning control sets for constrained motion planning in discrete state spaces, 2005 IEEE/RSJ Int. Conf. Intell. Rob. Syst., IEEE, 2005, pp. 3231–3237.
Hwan Jeon, J., Karaman, S., and Frazzoli, E., Anytime computation of time-optimal off-road vehicle maneuvers using the RRT, 2011 50th IEEE Conf. Decis. Control & Eur. Control Conf., IEEE, 2011, pp. 3276–3282.
Webb, D.J. and Van Den Berg, J., Kinodynamic RRT*: asymptotically optimal motion planning for robots with linear dynamics, 2013 IEEE Int. Conf. Rob. Autom., IEEE, 2013, pp. 5054–5061.
Flores, M.E. and Milam, M.B., Trajectory generation for differentially flat systems via NURBS basis functions with obstacle avoidance, 2006 Am. Control Conf., IEEE, 2006, pp. 5769–5775.
Rufli, M., Ferguson, D., and Siegwart, R., Smooth path planning in constrained environments, 2009 IEEE Int. Conf. Rob. Autom., IEEE, 2009, pp. 3780–3785.
Silver, D., Cooperative pathfinding, Proc. AAAI Conf. Artif. Intell. Interact. Digital Entertainment, 2005, vol. 1, no. 1, pp. 117–122.
Isidori, A., Nonlinear Control Systems, Berlin: Springer, 1995.
Khalil, H.K., Nonlinear Systems, Upper Saddle River, NJ: Prentice Hall, 2002, 3rd ed.
Utkin, V.I., Sliding mode control design principles and applications to electric drives, IEEE Trans. Ind. Electron., 1993, vol. 40, no. 1, pp. 23–36.
Yu, S. et al., MPC for path following problems of wheeled mobile robots, IFAC-PapersOnLine, 2018, vol. 51, no. 20, pp. 247–252.
Fliess, M. et al., Flatness and defect of non-linear systems: introductory theory and examples, Int. J. Control, 1995, vol. 61, no. 6, pp. 1327–1361.
Bascetta, L., Arrieta, I.M., and Prandini, M., Flat-RRT*: a sampling-based optimal trajectory planner for differentially flat vehicles with constrained dynamics, IFAC-PapersOnLine, 2017, vol. 50, no. 1, pp. 6965–6970.
Sahoo, S.R. and Chiddarwar, S.S., Mobile robot control using bond graph and flatness based approach, Procedia Comput. Sci., 2018, vol. 133, pp. 213–221.
Chetverikov, V.N., Flatness of dynamically linearizable systems, Differ. Equations, 2004, vol. 40, no. 12, pp. 1747–1756.
Belinskaya, Yu.S. and Chetverikov, V.N., Covering method for terminal control with regard of constraints, Differ. Equations, 2014, vol. 50, no. 12, pp. 1632–1642.
Tang, C.P., Differential flatness-based kinematic and dynamic control of a differentially driven wheeled mobile robot, 2009 IEEE Int. Conf. Rob. Biomimetics (ROBIO), IEEE, 2009, pp. 2267–2272.
Andersson, O. et al., Receding-horizon lattice-based motion planning with dynamic obstacle avoidance, 2018 IEEE Conf. Decis. Control (CDC), IEEE, 2018, pp. 4467–4474.
Belinskaya, Y.S. and Chetverikov, V.N., Covering method for point-to-point control of constrained flat systems, IFAC-PapersOnLine, 2015, vol. 48, no. 11, pp. 924–929.
Yap, P., Grid-based path-finding, Conf. Can. Soc. Comput. Studies Intell., Berlin–Heidelberg: Springer, 2002, pp. 44–55.
Hart, P.E., Nilsson, N.J., and Raphael, B., A formal basis for the heuristic determination of minimum cost paths, IEEE Trans. Syst. Sci. Cybern., 1968, vol. 4, no. 2, pp. 100–107.
Cohen, L. et al., Optimal and bounded-suboptimal multi-agent motion planning, 12th Annu. Symp. Comb. Search, 2019, pp. 44–51.
Sturtevant, N.R., Benchmarks for grid-based pathfinding, IEEE Trans. Comput. Intell. AI Games, 2012, vol. 4, no. 2, pp. 144–148.
Author information
Authors and Affiliations
Corresponding authors
Additional information
The code is open sourced: bit.ly/3mEBK59.
The video-demo can be found at youtu.be/cYm3Q1tHRnU.
Translated by The Author(s)
Rights and permissions
About this article
Cite this article
Yakovlev, K.S., Andreychuk, A.A., Belinskaya, J.S. et al. Safe Interval Path Planning and Flatness-Based Control for Navigation of a Mobile Robot among Static and Dynamic Obstacles. Autom Remote Control 83, 903–918 (2022). https://doi.org/10.1134/S000511792206008X
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S000511792206008X