Skip to main content
Top

2016 | OriginalPaper | Chapter

Multi-agent Poli-RRT*

Optimal Constrained RRT-based Planning for Multiple Vehicles with Feedback Linearisable Dynamics

Authors : Matteo Ragaglia, Maria Prandini, Luca Bascetta

Published in: Modelling and Simulation for Autonomous Systems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Planning a trajectory that is optimal according to some performance criterion, collision-free, and feasible with respect to dynamic and actuation constraints is a key functionality of an autonomous vehicle. Poli-RRT* is a sample-based planning algorithm that serves this purpose for a single vehicle with feedback linearisable dynamics. This paper extends Poli-RRT* to a multi-agent cooperative setting where multiple vehicles share the same environment and need to avoid each other besides some static obstacles.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Pivtoraiko, M., Knepper, R., Kelly, A.: Differentially constrained mobile robot motion planning in state lattices. J. Field Robot. 26, 308–333 (2009)CrossRef Pivtoraiko, M., Knepper, R., Kelly, A.: Differentially constrained mobile robot motion planning in state lattices. J. Field Robot. 26, 308–333 (2009)CrossRef
2.
go back to reference Likhachev, M., Ferguson, D.: Planning long dynamically feasible maneuvers for autonomous vehicles. Int. J. Robot. Res. 28, 933–945 (2009)CrossRef Likhachev, M., Ferguson, D.: Planning long dynamically feasible maneuvers for autonomous vehicles. Int. J. Robot. Res. 28, 933–945 (2009)CrossRef
3.
go back to reference Tahirovic, A., Magnani, G.: General framework for mobile robot navigation using passivity-based MPC. IEEE Trans. Autom. Control 56, 184–190 (2011)MathSciNetCrossRef Tahirovic, A., Magnani, G.: General framework for mobile robot navigation using passivity-based MPC. IEEE Trans. Autom. Control 56, 184–190 (2011)MathSciNetCrossRef
4.
go back to reference LaValle, S.M., Kuffner, J.J.: Randomized kinodynamic planning. Int. J. Robot. Res. 20, 378–400 (2001)CrossRef LaValle, S.M., Kuffner, J.J.: Randomized kinodynamic planning. Int. J. Robot. Res. 20, 378–400 (2001)CrossRef
5.
go back to reference Barraquand, J., Kavraki, L., Latombe, J., Motwani, R., Li, T., Raghavan, P.: A random sampling scheme for path planning. Int. J. Robot. Res. 16, 759–774 (1997)CrossRef Barraquand, J., Kavraki, L., Latombe, J., Motwani, R., Li, T., Raghavan, P.: A random sampling scheme for path planning. Int. J. Robot. Res. 16, 759–774 (1997)CrossRef
6.
go back to reference Branicky, M., Curtiss, M., Levine, J., Morgan, S.: RRTs for nonlinear, discrete, and hybrid planning and control. In: IEEE Conference on Decision and Control (CDC), vol. 1, pp. 657–663 (2003) Branicky, M., Curtiss, M., Levine, J., Morgan, S.: RRTs for nonlinear, discrete, and hybrid planning and control. In: IEEE Conference on Decision and Control (CDC), vol. 1, pp. 657–663 (2003)
7.
go back to reference Branicky, M., Curtiss, M., Levine, J., Morgan, S.: Sampling-based planning, control and verification of hybrid systems. IEEE Proc. Control Theory Appl. 153, 575–590 (2006)CrossRef Branicky, M., Curtiss, M., Levine, J., Morgan, S.: Sampling-based planning, control and verification of hybrid systems. IEEE Proc. Control Theory Appl. 153, 575–590 (2006)CrossRef
8.
go back to reference Karaman, S., Frazzoli, E.: Optimal kinodynamic motion planning using incremental sampling-based methods. In: IEEE Conference on Decision and Control (CDC), Atlanta, GA (2010) Karaman, S., Frazzoli, E.: Optimal kinodynamic motion planning using incremental sampling-based methods. In: IEEE Conference on Decision and Control (CDC), Atlanta, GA (2010)
9.
go back to reference Karaman, S., Frazzoli, E.: Incremental sampling-based algorithms for optimal motion planning. In: Robotics: Science and Systems (RSS), Zaragoza, Spain (2010) Karaman, S., Frazzoli, E.: Incremental sampling-based algorithms for optimal motion planning. In: Robotics: Science and Systems (RSS), Zaragoza, Spain (2010)
10.
go back to reference Karaman, S., Walter, M., Perez, A., Frazzoli, E., Teller, S.: Real-time motion planning using the RRT*. In: IEEE International Conference on Robotics and Automation (ICRA) (2011) Karaman, S., Walter, M., Perez, A., Frazzoli, E., Teller, S.: Real-time motion planning using the RRT*. In: IEEE International Conference on Robotics and Automation (ICRA) (2011)
11.
go back to reference Karaman, S., Frazzoli, E.: Sampling-based algorithms for optimal motion planning. Int. J. Robot. Res. 30, 846–894 (2011)CrossRefMATH Karaman, S., Frazzoli, E.: Sampling-based algorithms for optimal motion planning. Int. J. Robot. Res. 30, 846–894 (2011)CrossRefMATH
12.
go back to reference Karaman, S., Frazzoli, E.: Sampling-based optimal motion planning with deterministic \(\mu \)-calculus specifications. In: American Control Conference (ACC) (2012) Karaman, S., Frazzoli, E.: Sampling-based optimal motion planning with deterministic \(\mu \)-calculus specifications. In: American Control Conference (ACC) (2012)
13.
go back to reference Perez, A., Karaman, S., Walter, M., Shkolnik, A., Frazzoli, E., Teller, S.: Asymptotically-optimal path planning for manipulation using incremental sampling-based algorithms. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (2011) Perez, A., Karaman, S., Walter, M., Shkolnik, A., Frazzoli, E., Teller, S.: Asymptotically-optimal path planning for manipulation using incremental sampling-based algorithms. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (2011)
14.
go back to reference hwan Jeon, J., Karaman, S., Frazzoli, E.: Anytime computation of time-optimal off-road vehicle maneuvers using the RRT*. In: IEEE Conference on Decision and Control and European Control Conference (CDC-ECC), pp. 3276–3282 (2011) hwan Jeon, J., Karaman, S., Frazzoli, E.: Anytime computation of time-optimal off-road vehicle maneuvers using the RRT*. In: IEEE Conference on Decision and Control and European Control Conference (CDC-ECC), pp. 3276–3282 (2011)
15.
go back to reference Press, W., Teukolsky, S., Vetterling, W., Flannery, B.: Numerical Recipes: The Art of Scientific Computing. Cambridge University Press, Cambridge (2007)MATH Press, W., Teukolsky, S., Vetterling, W., Flannery, B.: Numerical Recipes: The Art of Scientific Computing. Cambridge University Press, Cambridge (2007)MATH
16.
go back to reference Webb, D., van den Berg, J.: Kinodynamic RRT*: asymptotically optimal motion planning for robots with linear dynamics. In: IEEE Intenrational Conference on Robotics and Automation (ICRA), pp. 5054–5061 (2013) Webb, D., van den Berg, J.: Kinodynamic RRT*: asymptotically optimal motion planning for robots with linear dynamics. In: IEEE Intenrational Conference on Robotics and Automation (ICRA), pp. 5054–5061 (2013)
17.
go back to reference Perez, A., Platt, R., Konidaris, G., Kaelbling, L., Lozano-Perez, T.: LQR-RRT*: optimal sampling-based motion planning with automatically derived extension heuristics. In: IEEE International Conference on Robotics and Automation (ICRA), pp. 2537–2542 (2012) Perez, A., Platt, R., Konidaris, G., Kaelbling, L., Lozano-Perez, T.: LQR-RRT*: optimal sampling-based motion planning with automatically derived extension heuristics. In: IEEE International Conference on Robotics and Automation (ICRA), pp. 2537–2542 (2012)
18.
go back to reference Goretkin, G., Perez, A., Platt, R., Konidaris, G.: Optimal sampling-based planning for linear-quadratic kinodynamic systems. In: IEEE International Conference on Robotics and Automation (ICRA) (2013) Goretkin, G., Perez, A., Platt, R., Konidaris, G.: Optimal sampling-based planning for linear-quadratic kinodynamic systems. In: IEEE International Conference on Robotics and Automation (ICRA) (2013)
19.
go back to reference Ragaglia, M., Prandini, M., Bascetta, L.: Poli-RRT*: optimal RRT-based planning for constrained and feedback linearisable vehicle dynamics. In: European Control Conference (ECC) (2015) Ragaglia, M., Prandini, M., Bascetta, L.: Poli-RRT*: optimal RRT-based planning for constrained and feedback linearisable vehicle dynamics. In: European Control Conference (ECC) (2015)
20.
go back to reference Stipanovic, D., Inalhan, G., Teo, R., Tomlin, C.: Decentralized overlapping control of a formation of unmanned aerial vehicles. Automatica 40, 1285–1296 (2004)MathSciNetCrossRefMATH Stipanovic, D., Inalhan, G., Teo, R., Tomlin, C.: Decentralized overlapping control of a formation of unmanned aerial vehicles. Automatica 40, 1285–1296 (2004)MathSciNetCrossRefMATH
Metadata
Title
Multi-agent Poli-RRT*
Authors
Matteo Ragaglia
Maria Prandini
Luca Bascetta
Copyright Year
2016
DOI
https://doi.org/10.1007/978-3-319-47605-6_21

Premium Partner