Discovering Options That Minimize Average Planning Time
Abstract
We present an option discovery algorithm that accelerates planning by minimizing the shortest distance between any two states in the MDP. The proposed algorithm produces options that approximately minimize planning time in the multi-goal setting: it is shown to be a worst case (4-alpha, 2)-approximation of the optimal option set, where alpha is the approximation ratio of the k-medians with penalties subroutine. We then present a variation, "Fast Average Options", with improved run-time and describe a general means of producing similar algorithms based on selection of a k-medians subroutine. We empirically evaluate our method on four discrete and two continuous control planning domains and show that it outperforms other leading option discovery algorithms.
Cite
Text
Ivanov et al. "Discovering Options That Minimize Average Planning Time." AAAI Conference on Artificial Intelligence, 2025. doi:10.1609/AAAI.V39I17.33932Markdown
[Ivanov et al. "Discovering Options That Minimize Average Planning Time." AAAI Conference on Artificial Intelligence, 2025.](https://mlanthology.org/aaai/2025/ivanov2025aaai-discovering/) doi:10.1609/AAAI.V39I17.33932BibTeX
@inproceedings{ivanov2025aaai-discovering,
title = {{Discovering Options That Minimize Average Planning Time}},
author = {Ivanov, Alexander and Bagaria, Akhil and Konidaris, George},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2025},
pages = {17573-17581},
doi = {10.1609/AAAI.V39I17.33932},
url = {https://mlanthology.org/aaai/2025/ivanov2025aaai-discovering/}
}