Integrating temporal reasoning and Sampling-Based motion planning for multigoal problems with dynamics and time windows

TY - JOUR

T1 - Integrating temporal reasoning and Sampling-Based motion planning for multigoal problems with dynamics and time windows

AU - Edelkamp, Stefan

AU - Lahijanian, Morteza

AU - Magazzeni, Daniele

AU - Plaku, Erion

PY - 2018/10/1

Y1 - 2018/10/1

N2 - Robots used for inspection, package deliveries, moving of goods, and other logistics operations are often required to visit certain locations within specified time bounds. This gives rise to a challenging problem as it requires not only planning collision-free and dynamically feasible motions but also reasoning temporally about when and where the robot should be. While significant progress has been made in integrating task and motion planning, there are still no effective approaches for multigoal motion planning when both dynamics and time windows must be satisfied. To effectively solve this challenging problem, this paper develops an approach that couples temporal planning over a discrete abstraction with sampling-based motion planning over the continuous state space of feasible motions. The discrete abstraction is obtained by imposing a roadmap that captures the connectivity of the free space. At each iteration of a core loop, the approach first invokes the temporal planner to find a solution over the roadmap abstraction. In a second step, the approach uses sampling to expand a motion tree along the regions associated with the discrete solution. Experiments are conducted with second-order ground and aerial vehicle models operating in complex environments. Results demonstrate the efficiency and scalability of the approach as we increase the number of goals and the difficulty of satisfying the time bounds.

AB - Robots used for inspection, package deliveries, moving of goods, and other logistics operations are often required to visit certain locations within specified time bounds. This gives rise to a challenging problem as it requires not only planning collision-free and dynamically feasible motions but also reasoning temporally about when and where the robot should be. While significant progress has been made in integrating task and motion planning, there are still no effective approaches for multigoal motion planning when both dynamics and time windows must be satisfied. To effectively solve this challenging problem, this paper develops an approach that couples temporal planning over a discrete abstraction with sampling-based motion planning over the continuous state space of feasible motions. The discrete abstraction is obtained by imposing a roadmap that captures the connectivity of the free space. At each iteration of a core loop, the approach first invokes the temporal planner to find a solution over the roadmap abstraction. In a second step, the approach uses sampling to expand a motion tree along the regions associated with the discrete solution. Experiments are conducted with second-order ground and aerial vehicle models operating in complex environments. Results demonstrate the efficiency and scalability of the approach as we increase the number of goals and the difficulty of satisfying the time bounds.

KW - autonomous vehicle navigation

KW - Motion and path planning

KW - motion control

KW - task planning

UR - https://www.scopus.com/pages/publications/85063310411

U2 - 10.1109/LRA.2018.2853642

DO - 10.1109/LRA.2018.2853642

M3 - Article

AN - SCOPUS:85063310411

SN - 2377-3766

VL - 3

SP - 3473

EP - 3480

JO - IEEE Robotics and Automation Letters

JF - IEEE Robotics and Automation Letters

IS - 4

M1 - 8405360

ER -