Abstract
This paper discusses a particle swarm optimization (PSO)-based motion-planning algorithm in a multiple-vehicle system that minimizes the traveling time of the slowest vehicle by considering, as constraints, the radial and tangential accelerations and maximum linear velocities of all vehicles. A class of continuous-curvature curvesthree-degree Bezier curvesis selected as the basic shape of the vehicle trajectories to minimize the number of parameters required to express them mathematically. In addition, velocity profile generation using the local minimum of the radial-accelerated linear velocity profile, which reduces the calculation effort, is introduced. A new PSO-based search algorithm, called “particle-group-based PSO,” is introduced to find the best combination of trajectories that minimizes the traveling time of the slowest vehicle. A particle group is designed to wrap a set of particles representing each vehicle. The first and last two control points characterizing a curve are used as the state vector of a particle. Simulation results demonstrating the performance of the proposed method are presented. The main advantage of the proposed method is its minimization of the velocity-profile-generation time, and thereby, its maximization of the search time.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
T. Fraichard and A. Scheuer, “From Reeds and Shepps to continuous-curvature paths,” IEEE Transactions on Robotics, vol. 20, no. 6, pp. 1025–1035, December 2004.
Y. J. Kanayama and B. I. Hartman, “Smooth local-path planning for autonomous vehicles,” International Journal of Robotics Research, vol. 16, no. 3, pp. 263–284, 1997.
K. G. Jolly, R. S. Kumar, and R. Vijayakumar, “A Bezier curve based path planning in a multi-agent robot soccer system without violating the acceleration limits,” Robotics and Autonomous Systems, vol. 57, no. 1, pp. 23–33, 2009.
C. G. Lo Bianco and O. Gerelli, “Generation of paths with minimum curvature derivative with η3-splines,” IEEE Transactions on Automation Science and Engineering, vol. 7, no. 2, pp. 249–256, 2010.
M. Haddad, T. Chettibi, S. Hanchi, and H. E. Lehtihet, “A random-profile approach for trajectory planning of wheeled mobile robot,” European Journal of Mechanics A/Solid, vol. 26, no. 3, pp. 519–540, 2007.
M. Haddad, W. Khalil, and H. E. Lehtihet, “Trajectory planning of unicycle mobile robots with a trapezoidalvelocity constraint,” IEEE Transactions on Robotics, vol. 26, no. 5, pp. 954–962, 2010.
G. Klancar and I. Skrjanc, “A case study of the collision-avoidance problem based on Bernstein-Bezier path tracking for multiple robots with known constraints,” Journal of Intelligent & Robot Systems, vol. 60, no. 2, pp. 317–337, 2010.
M. Lepetic, G. Klancar, I. Skrjanc, D. Matko, and B. Potocnik, “Time optimal path planning considering acceleration limits,” Robotics and Autonomous Systems, vol. 45, no. 3–4, pp. 199–210, 2003.
W. Yu, W. Shuo, W. Rui, and T. Min, “Generation of spatial-temporal Bezier curve for simultaneous arrival of multiple unmanned vehicles,” Information Sciences, vol. 418–419, pp. 34–45, 2017.
Q. C. Nguyen, Y. Kim, and H. Kwon, “Optimization of layout and path planning of surgical robotic system,” International Journal of Control, Automation and System, vol. 15, no. 1, pp. 375–384, February 2017.
J. Faigl and P. Vana, “Surveillance planning with Bezier curve,” IEEE Robotics and Automation Letters, vol. 3, no. 2, pp. 750–757, April 2018.
S. M. LaValle and J. J. Kuffner, Jr., “Randomized Kino-dynamic Planning,” International Journal of Robotics Research, vol. 20, no. 5, pp. 378–400, May 2001.
A. K. Pamosoaji and K.-S. Hong, “A path-planning algorithm using vector potential functions in triangular regions,” IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 43, no. 4, pp. 832–842, 2013.
A. Widyotriatmo and K.-S. Hong, “A navigation function-based control of multiple wheeled robots,” IEEE Transactions on Industrial Electronics, vol. 47, no. 4, pp. 722–732, 2011.
A. Widyotriatmo and K.-S. Hong, “Switching algorithm for robust configuration control of a wheeled vehicle,” Control Engineering Practice, vol. 20, no. 3, pp. 315–325, 2012.
Y.-S. Kim and K.-S. Hong, “A tracking algorithm for autonomous navigation of AGVs in an automated container terminal,” Journal of Mechanical Science and Technology, vol. 19, no. 1, pp. 72–86, January 2005.
A. Widyotriatmo, B. Hong, and K.-S. Hong, “Predictive navigation of an autonomous vehicle with nonholonomic and minimum turning radius constraints,” Journal of Mechanical Science and Technology, vol. 23, no. 2, pp. 381–388, February 2009.
K.-S. Hong and J. Bentsman, “Direct adaptive control of parabolic systems: Algorithm synthesis, and convergence and stability analysis,” IEEE Transactions on Automatic Control, vol. 39, no. 10, pp. 2018–2033, October 1994.
K.-S. Hong, “An open-loop control for underactuated manipulators using oscillatory inputs: steering capability of an unactuated joint,” IEEE Transactions on Control Systems Technology, vol. 10, no. 3, pp. 469–480, August 2002.
K.-S. Hong, T. A. Tamba, and J.-B. Song, “Mobile robot control architecture for reflexive avoidance of moving obstacles,” Advanced Robotics, vol. 22, pp. 1397–1420, April 2008.
A. K. Pamosoaji, P. T. Cat, and K.-S. Hong, “Sliding mode and proportional-derivative-type motion control with radial basis function neural basis function neural network based estimators for wheeled vehicles,” International Journal of Systems and Science, vol. 45, no. 12, pp. 2515–2528, July 2014.
S. Islam, P. X. Liu, and A. E. Saddik., “Nonlinear robust adaptive sliding mode control design for miniature unmanned multirotor aerial vehicle,” International Journal of Control, Automation and System, vol. 15, no. 4, pp. 1661–1668, August 2017.
B. V. Galbraith, F. H. Guenther, and M. Versace, “A neural network-based exploratory learning and motor planning system for co-robots,” Frontiers in Neurorobotics, vol. 9, no. 7, pp. 1–14, July 2015.
T. T. Q. Bui and K.-S. Hong, “Evaluating a color-based active basis model for object recognition,” Computer Vision and Image Understanding, vol. 116, no. 11, pp. 1111–1120, November 2012.
E. Grinke, C. Tetzlaff, F. Wörgötter, and P. Manoonpong, “Synaptic plasticity in a recurrent neural network for versatile and adaptive behaviors of a walking robot,” Frontiers in Neurorobotics, vol. 9, no. 11, pp. 1–15, October 2015.
M. Frank, J. Leitner, M. Stollenga, A. Förster, and J. Schmidhuber, “Curiosity driven reinforcement learning for motion planning on humanoids,” Frontiers in Neurorobotics, vol. 7, pp. 1–15, January 2014.
K.-S. Hong and N. Nasser, “Reduction of delay in detecting initial dips from functional near-infrared spectroscopy signals using vector-based phase analysis,” International Journal of Neural Systems, vol. 26, no. 3 (article number: 1640012), pp. 1–16, January 2016.
E. K. Xidias and P. N. Azariadis, “Mission design for a group of autonomous guided vehicles,” Robotics and Autonomous Systems, vol. 59, no. 1, pp. 34–43, January 2011.
J. Banfi, N. Basilico, and F. Amigoni, “Intractability of time-optimal multirobot path planning on 2D grid graph with holes,” IEEE Robotics and Automation Letters, vol. 2, no. 4, pp. 1941–1947, June 2017.
X. C. Ding, A. R. Rahmani, and M. Egerstedt, “Multi-UAV convoy protection: an optimal approach to path planning and coordination,” IEEE Transactions on Robotics, vol. 26, no. 2, pp. 256–268, March 2010.
J. Peng and S. Akella, “Coordinating multiple robots with kinodynamic constraints along specified paths,” International Journal of Robotics Research, vol. 24, no. 4, pp. 295–310, April 2005.
K. E. Bekris, D. K. Grady, M. Moll, and L. E. Kavraki, “Safe distributed motion coordination for second-order systems with different planning cycles,” International Journal of Robotics Research, vol. 31, no. 2, pp. 129–150, February 2012.
Y. Cai and S. X. Yang, “An improved PSO-based approach with dynamic parameter tuning for cooperative multi-robot target searching in complex unknown environments,” International Journal of Control, vol. 86, no. 10, pp. 1720–1732, May 2013.
V. Sharma, M. Savchenko, E. Frazzoli, and P. G. Voulgaris, “Transfer time complexity of conflict-free vehicle routing with no communications,” International Journal of Robotics Research, vol. 26, no. 3, pp. 255–271, March 2007.
M. Clerc and J. Kennedy, “The particle swarm–explosion, stability, and convergence in a multidimensional complex space,” IEEE Transactions on Evolutionary Computation, vol. 6, no. 1, pp. 58–73, February 2002.
P. Yang, R. Gao, X. Pan, and T. Li, “Study on sliding mode fault tolerant predictive control based on multi agent particle swarm optimization,” International Journal of Control, Automation and Systems, vol. 15, no. 5, pp. 2034–2042, October 2017.
W. Ye, W. Feng, and S. Fan, “A novel multi-swarm particle swarm optimization with dynamic learning strategy,” Applied Soft Computing, vol. 61, pp. 832–843, December 2017.
F. Wang, H. Zhang, K. Li, Z. Lin, J. Yang, and X.-L. Shen, “A hybrid particle swarm optimization algorithm using adaptive learning strategy,” Information Sciences, vol. 436–437, pp. 162–177, April 2018.
Y. Chen and D. Wang, “Forecasting by general type-2 fuzzy logic systems optimized with QPSO algorithms,” International Journal of Control, Automation and Systems, vol. 15, no. 6, pp. 2950–2958, December 2017.
H. Freire, P. B. M. Oliveira, and E. J. S. Pires, “From single to many-objective PID controller design using particle swarm optimization,” International Journal of Control, Automation and Systems, vol. 15, no. 2, pp. 918–932, April 2017.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Recommended by Associate Editor Augie Widyotriatmo. This work was supported by the National Research Foundation of Korea under the auspices of the Ministry of Science and ICT, Republic of Korea (grant no. NRF-2017R1A2A1A17069430).
Anugrah K. Pamosoaji received his B. Eng. and M. Eng. degrees in Electrical Engineering from the Institut Teknologi Bandung (ITB), Indonesia, in 2003 and 2006, respectively. He is a Ph.D. student in the School of Mechanical Engineering, Pusan National University. Recently, he is with Department of Industrial Engineering, Faculty of Industrial Technology, Universitas Atma Jaya Yogyakarta (UAJY), Indonesia. His research interests include robotics, path and trajectory planning, robotics control systems, mobile robots, and multiple-vehicle systems.
Mingxu Piao received the B.S. degree in Mechanical Engineering Department from Shanghai Maritime University, China, in 2010. He is currently an integrated Master and Ph.D. student in the School of Mechanical Engineering, Pusan National University, Korea. His research interests include sliding mode control, adaptive control, robotics, port automation, and crane control.
Keum-Shik Hong Please see vol. 13, no. 2, p. 425, April, 2015 of this journal.
Rights and permissions
About this article
Cite this article
Pamosoaji, A.K., Piao, M. & Hong, KS. PSO-based Minimum-time Motion Planning for Multiple Vehicles Under Acceleration and Velocity Limitations. Int. J. Control Autom. Syst. 17, 2610–2623 (2019). https://doi.org/10.1007/s12555-018-0176-9
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12555-018-0176-9