Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en van den Berg, Jur; Overmars, Mark License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-8733


Computing Shortest Safe Path amidst Growing Discs in the Plane



In this paper we discuss the problem of planning safe paths amidst unpredictably moving obstacles in the plane. Given the initial positions and the maximal velocities of the moving obstacles, the regions that are possibly not collision-free are modeled by discs that grow over time. We present an approach to compute the shortest path between two points in the plane that avoids these growing discs. The generated paths are thus guaranteed to be collision-free with respect to the moving obstacles while being executed. We created a fast implementation that is capable of planning paths amidst many growing discs within milliseconds.

BibTeX - Entry

  author =	{Jur van den Berg and Mark Overmars},
  title =	{Computing Shortest Safe Path amidst Growing Discs in the Plane},
  booktitle =	{Robot Navigation},
  year =	{2007},
  editor =	{S{\'a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  number =	{06421},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{},
  annote =	{Keywords: Path planning dynamic environments}

Keywords: Path planning dynamic environments
Seminar: 06421 - Robot Navigation
Related Scholarly Article:
Issue date: 2007
Date of publication: 2007

DROPS-Home | Fulltext Search | Imprint Published by LZI