OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Open Loop Execution of Tree-Search Algorithms

Lecarpentier, Erwan and Infantes, Guillaume and Lesire, Charles and Rachelson, Emmanuel Open Loop Execution of Tree-Search Algorithms. (2018) In: 2018 International Joint Conference on Artificial Intelligence (IJCAI 2018), 13 July 2018 - 19 July 2018 (Stockholm, Sweden).

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: https://doi.org/10.24963/ijcai.2018/327


In the context of tree-search stochastic planning algorithms where a generative model is available, we consider on-line planning algorithms building trees in order to recommend an action. We investigate the question of avoiding re-planning in subsequent decision steps by directly using sub-trees as action recommender. Firstly, we propose a method for open loop control via a new algorithm taking the decision of re-planning or not at each time step based on an analysis of the statistics of the sub-tree. Secondly, we show that the probability of selecting a suboptimal action at any depth of the tree can be upper bounded and converges towards zero. Moreover, this upper bound decays in a logarithmic way between subsequent depths. This leads to a distinction between node-wise optimality and state-wise optimality. Finally, we empirically demonstrate that our method achieves a compromise between loss of performance and computational gain.

Item Type:Conference or Workshop Item (Paper)
Additional Information:ISBN (Online): 978-0-9992411-2-7
HAL Id:hal-01902685
Audience (conference):International conference proceedings
Uncontrolled Keywords:
Institution:Université de Toulouse > Institut Supérieur de l'Aéronautique et de l'Espace - ISAE-SUPAERO (FRANCE)
French research institutions > Office National d'Etudes et Recherches Aérospatiales - ONERA (FRANCE)
Laboratory name:
Région Occitanie
Deposited On:23 Oct 2018 14:52

Repository Staff Only: item control page