In collaboration with The Jerusalem College of Technology

Shortest path for K-Goals

Roni Stern, Meir Goldenberg, Ariel Felner

SoCS-2017 short paper

The k-goal problem is a generalization of the Shortest
Path Problem (SPP) in which the task is to solve k SPP problems,
such that all the problems share the same start vertex.
kGP was introduced to the heuristic search community for
building an Incremental Roadmap Spanner technique (Dobson
and Bekris 2014), which is a useful construct in motion
plannin for robotics. But kGP has many other applications,
e.g., when path planning for multiple drones flying from a
central dispatcher location to k target locations.

Download
PDF