Optimal path-planning under finite memory obstacle dynamics based on probabilistic finite state automata models

Ishanu Chattopadhyay; Asok Ray

doi:10.1109/ACC.2009.5160369

Optimal path-planning under finite memory obstacle dynamics based on probabilistic finite state automata models

Ishanu Chattopadhyay, Asok Ray

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

Abstract

The v*-planning algorithm is generalized to handle finite memory obstacle dynamics. A sufficiently long observation sequence of obstacle dynamics is algorithmically compressed via Symbolic Dynamic Filtering to obtain a probabilistic finite state model which is subsequently integrated with the navigation automaton to generate an overall model reflecting both navigation constraints and obstacle dynamics. A v*-based solution then yields a deterministic plan that maximizes the difference of the probabilities of reaching the goal and of hitting an obstacle. The approach is validated by simulated solution of dynamic mazes.

Original language	English
Title of host publication	2009 American Control Conference, ACC 2009
Pages	2403-2408
Number of pages	6
DOIs	https://doi.org/10.1109/ACC.2009.5160369
State	Published - 2009
Event	2009 American Control Conference, ACC 2009 - St. Louis, MO, United States Duration: Jun 10 2009 → Jun 12 2009

Publication series

Name	Proceedings of the American Control Conference
ISSN (Print)	0743-1619

Conference

Conference	2009 American Control Conference, ACC 2009
Country/Territory	United States
City	St. Louis, MO
Period	6/10/09 → 6/12/09

Keywords

Language measure
Path planning
Probabilistic finite state machines
Robotics
Supervisory control

ASJC Scopus subject areas

Electrical and Electronic Engineering

Access to Document

10.1109/ACC.2009.5160369

Cite this

@inproceedings{2a8620843a5343f58e7bd381b656461e,

title = "Optimal path-planning under finite memory obstacle dynamics based on probabilistic finite state automata models",

abstract = "The v*-planning algorithm is generalized to handle finite memory obstacle dynamics. A sufficiently long observation sequence of obstacle dynamics is algorithmically compressed via Symbolic Dynamic Filtering to obtain a probabilistic finite state model which is subsequently integrated with the navigation automaton to generate an overall model reflecting both navigation constraints and obstacle dynamics. A v*-based solution then yields a deterministic plan that maximizes the difference of the probabilities of reaching the goal and of hitting an obstacle. The approach is validated by simulated solution of dynamic mazes.",

keywords = "Language measure, Path planning, Probabilistic finite state machines, Robotics, Supervisory control",

author = "Ishanu Chattopadhyay and Asok Ray",

year = "2009",

doi = "10.1109/ACC.2009.5160369",

language = "English",

isbn = "9781424445240",

series = "Proceedings of the American Control Conference",

pages = "2403--2408",

booktitle = "2009 American Control Conference, ACC 2009",

note = "2009 American Control Conference, ACC 2009 ; Conference date: 10-06-2009 Through 12-06-2009",

}

Chattopadhyay, I & Ray, A 2009, Optimal path-planning under finite memory obstacle dynamics based on probabilistic finite state automata models. in 2009 American Control Conference, ACC 2009., 5160369, Proceedings of the American Control Conference, pp. 2403-2408, 2009 American Control Conference, ACC 2009, St. Louis, MO, United States, 6/10/09. https://doi.org/10.1109/ACC.2009.5160369

Optimal path-planning under finite memory obstacle dynamics based on probabilistic finite state automata models. / Chattopadhyay, Ishanu; Ray, Asok.
2009 American Control Conference, ACC 2009. 2009. p. 2403-2408 5160369 (Proceedings of the American Control Conference).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Optimal path-planning under finite memory obstacle dynamics based on probabilistic finite state automata models

AU - Chattopadhyay, Ishanu

AU - Ray, Asok

PY - 2009

Y1 - 2009

N2 - The v*-planning algorithm is generalized to handle finite memory obstacle dynamics. A sufficiently long observation sequence of obstacle dynamics is algorithmically compressed via Symbolic Dynamic Filtering to obtain a probabilistic finite state model which is subsequently integrated with the navigation automaton to generate an overall model reflecting both navigation constraints and obstacle dynamics. A v*-based solution then yields a deterministic plan that maximizes the difference of the probabilities of reaching the goal and of hitting an obstacle. The approach is validated by simulated solution of dynamic mazes.

AB - The v*-planning algorithm is generalized to handle finite memory obstacle dynamics. A sufficiently long observation sequence of obstacle dynamics is algorithmically compressed via Symbolic Dynamic Filtering to obtain a probabilistic finite state model which is subsequently integrated with the navigation automaton to generate an overall model reflecting both navigation constraints and obstacle dynamics. A v*-based solution then yields a deterministic plan that maximizes the difference of the probabilities of reaching the goal and of hitting an obstacle. The approach is validated by simulated solution of dynamic mazes.

KW - Language measure

KW - Path planning

KW - Probabilistic finite state machines

KW - Robotics

KW - Supervisory control

UR - http://www.scopus.com/inward/record.url?scp=70449644252&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70449644252&partnerID=8YFLogxK

U2 - 10.1109/ACC.2009.5160369

DO - 10.1109/ACC.2009.5160369

M3 - Conference contribution

AN - SCOPUS:70449644252

SN - 9781424445240

T3 - Proceedings of the American Control Conference

SP - 2403

EP - 2408

BT - 2009 American Control Conference, ACC 2009

T2 - 2009 American Control Conference, ACC 2009

Y2 - 10 June 2009 through 12 June 2009

ER -

Optimal path-planning under finite memory obstacle dynamics based on probabilistic finite state automata models

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this