This paper presents a parallel computing implementation of the Iterative Dynamic Programming (IDP) solution to the multipoint Markov-Dubins problem using GPUs. The multipoint Markov-Dubins problem requires the computation of the shortest path with bounded curvature that connects a sequence of planar points (waypoints). As well as being interesting in its own right, an efficient solution to this problem is key to finding optimal or suboptimal solutions of other problems such as the Dubins Travelling Salesman and the Dubins Orienteering problem. The constraint on the curvature makes the problem highly non-linear and complicates its solution. Classic methods are optimisation-based and cast the problem into the Nonlinear Programming (NLP) or Mixed Integer Nonlinear Programming (MINLP) frameworks, for which existing solutions cannot be significantly parallelised. On the contrary, the IDP solution proposed here is well suited for parallel execution. In the paper, we show that the parallel implementation of the IDP outperforms both the NLP/MINLP methods and the iterative version of the IDP methods in terms of accuracy, computation time and power consumption. Computation time and power consumption will be the main focus of the paper, because they are closely related to the implementation on an embedded platform.

Robot motion planning: Can GPUs be a game changer? / Saccon, E.; Bevilacqua, P.; Fontanelli, D.; Frego, M.; Palopoli, L.; Passerone, R.. - STAMPA. - (2021), pp. 21-30. (Intervento presentato al convegno 45th IEEE Annual Computers, Software, and Applications Conference, COMPSAC 2021 tenutosi a esp nel 12-16, July, 2021) [10.1109/COMPSAC51774.2021.00015].

Robot motion planning: Can GPUs be a game changer?

Saccon E.;Bevilacqua P.;Fontanelli D.;Frego M.;Palopoli L.;Passerone R.
2021-01-01

Abstract

This paper presents a parallel computing implementation of the Iterative Dynamic Programming (IDP) solution to the multipoint Markov-Dubins problem using GPUs. The multipoint Markov-Dubins problem requires the computation of the shortest path with bounded curvature that connects a sequence of planar points (waypoints). As well as being interesting in its own right, an efficient solution to this problem is key to finding optimal or suboptimal solutions of other problems such as the Dubins Travelling Salesman and the Dubins Orienteering problem. The constraint on the curvature makes the problem highly non-linear and complicates its solution. Classic methods are optimisation-based and cast the problem into the Nonlinear Programming (NLP) or Mixed Integer Nonlinear Programming (MINLP) frameworks, for which existing solutions cannot be significantly parallelised. On the contrary, the IDP solution proposed here is well suited for parallel execution. In the paper, we show that the parallel implementation of the IDP outperforms both the NLP/MINLP methods and the iterative version of the IDP methods in terms of accuracy, computation time and power consumption. Computation time and power consumption will be the main focus of the paper, because they are closely related to the implementation on an embedded platform.
2021
Proceedings - 2021 IEEE 45th Annual Computers, Software, and Applications Conference, COMPSAC 2021
10662 LOS VAQUEROS CIRCLE, PO BOX 3014, LOS ALAMITOS, CA 90720-1264 USA
Institute of Electrical and Electronics Engineers Inc.
978-1-6654-2463-9
Saccon, E.; Bevilacqua, P.; Fontanelli, D.; Frego, M.; Palopoli, L.; Passerone, R.
Robot motion planning: Can GPUs be a game changer? / Saccon, E.; Bevilacqua, P.; Fontanelli, D.; Frego, M.; Palopoli, L.; Passerone, R.. - STAMPA. - (2021), pp. 21-30. (Intervento presentato al convegno 45th IEEE Annual Computers, Software, and Applications Conference, COMPSAC 2021 tenutosi a esp nel 12-16, July, 2021) [10.1109/COMPSAC51774.2021.00015].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/328820
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact