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 metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-01840583
Contributor : Olivier Buffet <>
Submitted on : Monday, July 16, 2018 - 2:57:47 PM
Last modification on : Friday, September 20, 2019 - 3:06:06 PM
Long-term archiving on: Wednesday, October 17, 2018 - 3:19:18 PM

File

JFPDA_2018_paper_2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01840583, version 1

Citation

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⟩

Share

Metrics

Record views

82

Files downloads

28