Shortest path for K-Goals

In collaboration with The Jerusalem College of Technology

Roni Stern, Meir Goldenberg, Ariel Felner

SoCS-2017 short paper

Link to document

The k-goal problem is a generalization of the ShortestPath 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 forbuilding an Incremental Roadmap Spanner technique (Dobsonand Bekris 2014), which is a useful construct in motionplannin for robotics. But kGP has many other applications,e.g., when path planning for multiple drones flying from acentral dispatcher location to k target locations.

Skip to content