The Bounded Acceleration Shortest Path problem: complexity and solution algorithms
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914745156632576 |
|---|---|
| author | Ardizzoni, Stefano Consolini, Luca Laurini, Mattia Locatelli, Marco |
| author_facet | Ardizzoni, Stefano Consolini, Luca Laurini, Mattia Locatelli, Marco |
| contents | 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: the nodes represent positions of a mobile vehicle and the 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 prove that BASP is NP-hard and define solution algorithm that achieves polynomial time-complexity under some additional hypotheses on problem data. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2103_02914 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | The Bounded Acceleration Shortest Path problem: complexity and solution algorithms Ardizzoni, Stefano Consolini, Luca Laurini, Mattia Locatelli, Marco Data Structures and Algorithms Systems and Control 90-08 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: the nodes represent positions of a mobile vehicle and the 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 prove that BASP is NP-hard and define solution algorithm that achieves polynomial time-complexity under some additional hypotheses on problem data. |
| title | The Bounded Acceleration Shortest Path problem: complexity and solution algorithms |
| topic | Data Structures and Algorithms Systems and Control 90-08 |
| url | https://arxiv.org/abs/2103.02914 |