Heuristic Search in Infinite State Spaces Guided by Lyapunov Analysis
Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence. Pages 242-246.
Abstract
In infinite state spaces, many standard heuristic search algorithms do not terminate if the problem is unsolvable. Under some conditions, they can fail to terminate even when there are solutions. We show how techniques from control theory, in particular Lyapunov stability analysis, can be employed to prove the existence of solution paths and provide guarantees that search algorithms will find those solutions. We study both optimal search algorithms, such as A*, and suboptimal/real-time search methods. A Lyapunov framework is useful for analyzing infinite-state search problems, and provides guidance for formulating search problems so that they become tractable for heuristic search. We illustrate these ideas with experiments using a simulated robot arm.
@inproceedings{ijcai2001p34,
title = {Heuristic Search in Infinite State Spaces Guided by Lyapunov Analysis},
author = {Perkins, Theodore J. and Barto, Andrew G.},
booktitle = {Proceedings of the Seventeenth International Joint Conference on
Artificial Intelligence, {IJCAI-01}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {242--246},
year = {2001},
url = {https://ijcai.org/proceedings/2001/34},
}
TY - CPAPER TI - Heuristic Search in Infinite State Spaces Guided by Lyapunov Analysis AU - Perkins, Theodore J. AU - Barto, Andrew G. T2 - Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, IJCAI-01 PB - International Joint Conferences on Artificial Intelligence PY - 2001 SP - 242 EP - 246 UR - https://ijcai.org/proceedings/2001/34 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
