Aarhus University Seal / Aarhus Universitets segl

Lukas Esterle

ARES: Adaptive receding-horizon synthesis of optimal plans

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer review

  • Anna Lukina, Vienna University of Technology
  • ,
  • Lukas Esterle
  • Christian Hirsch, Vienna University of Technology
  • ,
  • Ezio Bartocci, Vienna University of Technology
  • ,
  • Junxing Yang, Stony Brook University
  • ,
  • Ashish Tiwari, SRI International
  • ,
  • Scott A. Smolka, Stony Brook University
  • ,
  • Radu Grosu, Vienna University of Technology, Stony Brook University

We introduce ARES, an efficient approximation algorithm for generating optimal plans (action sequences) that take an initial state of a Markov Decision Process (MDP) to a state whose cost is below a specified (convergence) threshold. ARES uses Particle Swarm Optimization, with adaptive sizing for both the receding horizon and the particle swarm. Inspired by Importance Splitting, the length of the horizon and the number of particles are chosen such that at least one particle reaches a next-level state, that is, a state where the cost decreases by a required delta from the previous-level state. The level relation on states and the plans constructed by ARES implicitly define a Lyapunov function and an optimal policy, respectively, both of which could be explicitly generated by applying ARES to all states of the MDP, up to some topological equivalence relation. We also assess the effectiveness of ARES by statistically evaluating its rate of success in generating optimal plans. The ARES algorithm resulted from our desire to clarify if flying in V-formation is a flocking policy that optimizes energy conservation, clear view, and velocity alignment. That is, we were interested to see if one could find optimal plans that bring a flock from an arbitrary initial state to a state exhibiting a single connected V-formation. For flocks with 7 birds, ARES is able to generate a plan that leads to a V-formation in 95% of the 8,000 random initial configurations within 63 s, on average. ARES can also be easily customized into a model-predictive controller (MPC) with an adaptive receding horizon and statistical guarantees of convergence. To the best of our knowledge, our adaptive-sizing approach is the first to provide convergence guarantees in receding-horizon techniques.

OriginalsprogEngelsk
TitelTools and Algorithms for the Construction and Analysis of Systems - 23rd International Conference, TACAS 2017 held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Proceedings
RedaktørerTiziana Margaria, Axel Legay
Antal sider17
ForlagSpringer-Verlag
Udgivelsesår1 jan. 2017
Sider286-302
ISBN (trykt)9783662545799
DOI
StatusUdgivet - 1 jan. 2017
Eksternt udgivetJa
Begivenhed23rd International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2017 held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017 - Uppsala, Sverige
Varighed: 22 apr. 201729 apr. 2017

Konference

Konference23rd International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2017 held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017
LandSverige
By Uppsala
Periode22/04/201729/04/2017
SerietitelLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vol/bind10206 LNCS
ISSN0302-9743

Se relationer på Aarhus Universitet Citationsformater

ID: 170581677