Skip to Main content Skip to Navigation
New interface
Conference papers

Open Loop Execution of Tree-Search Algorithms

Abstract : 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 the sub-tree as an 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 subopti-mal 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download
Contributor : Olivier Buffet Connect in order to contact the contributor
Submitted on : Monday, July 16, 2018 - 2:57:47 PM
Last modification on : Wednesday, November 3, 2021 - 4:22:24 AM
Long-term archiving on: : Wednesday, October 17, 2018 - 3:19:18 PM


Files produced by the author(s)


  • HAL Id : hal-01840583, version 1


Erwan Lecarpentier, Guillaume Infantes, Charles Lesire, Emmanuel Rachelson. Open Loop Execution of Tree-Search Algorithms. Journées Francophones sur la Planification, la Décision et l'Apprentissage pour la conduite de systèmes 2018 (JFPDA 2018), Jul 2018, Nancy, France. ⟨hal-01840583⟩



Record views


Files downloads