Efficient solution algorithms for the Bounded Acceleration Shortest Path problem

The purpose of this work is to introduce and characterize the Bounded Acceleration Shortest Path (BASP) problem, a generalization of the Shortest Path (SP) problem. This problem is associated to a graph: nodes represent positions of a mobile vehicle and arcs are associated to pre-assigned geometric...

Full description

Saved in:
Bibliographic Details
Main Authors: Ardizzoni, Stefano, Consolini, Luca, Laurini, Mattia, Locatelli, Marco
Format: Conference Proceeding
Language:English
Subjects:
Conferences
Shortest path problem
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The purpose of this work is to introduce and characterize the Bounded Acceleration Shortest Path (BASP) problem, a generalization of the Shortest Path (SP) problem. This problem is associated to a graph: nodes represent positions of a mobile vehicle and arcs are associated to pre-assigned geometric paths that connect these positions. BASP consists in finding the minimum-time path between two nodes. Differently from SP, we require that the vehicle satisfy bounds on maximum and minimum acceleration and speed, that depend on the vehicle position on the currently traveled arc. We propose solution algorithms that achieves polynomial time-complexity under some additional hypotheses on problem data.
ISSN:2576-2370
DOI:10.1109/CDC45484.2021.9683191