Simplicial Label Correcting Algorithms for continuous stochastic shortest path problems

Dmitry S. Yershov, Steven M Lavalle

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The problem of optimal feedback planning under prediction uncertainties among static obstacles is considered. A discrete-time stochastic state transition model is defined over a continuous state space. A relation to a continuous 'nearby' deterministic model is proven for small time steps; the cost-to-go function of the stochastic model is approximated with that of the deterministic model, and the approximation error is found to be proportional to the time step. This motivates using numerical methods, which are vastly available for solving deterministic problems, to approximate the original stochastic problem. We demonstrate this application using a Simplicial Label Correcting Algorithm. This algorithms uses a piecewise linear discretization to compute the shortest-path plan on a simplicial complex. Additionally, the theoretical error bound between the approximate solution and the exact solution is derived and confirmed during numerical experiments. This paper provides a rigorous analysis as well as algorithmic and implementation details of the proposed model for the stochastic shortest path problem in continuous spaces with obstacles.

Original languageEnglish (US)
Title of host publication2013 IEEE International Conference on Robotics and Automation, ICRA 2013
Pages5062-5067
Number of pages6
DOIs
StatePublished - Nov 14 2013
Event2013 IEEE International Conference on Robotics and Automation, ICRA 2013 - Karlsruhe, Germany
Duration: May 6 2013May 10 2013

Publication series

NameProceedings - IEEE International Conference on Robotics and Automation
ISSN (Print)1050-4729

Other

Other2013 IEEE International Conference on Robotics and Automation, ICRA 2013
CountryGermany
CityKarlsruhe
Period5/6/135/10/13

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Simplicial Label Correcting Algorithms for continuous stochastic shortest path problems'. Together they form a unique fingerprint.

  • Cite this

    Yershov, D. S., & Lavalle, S. M. (2013). Simplicial Label Correcting Algorithms for continuous stochastic shortest path problems. In 2013 IEEE International Conference on Robotics and Automation, ICRA 2013 (pp. 5062-5067). [6631300] (Proceedings - IEEE International Conference on Robotics and Automation). https://doi.org/10.1109/ICRA.2013.6631300