ARES: Adaptive receding-horizon synthesis of optimal plans

Anna Lukina*, Lukas Esterle, Christian Hirsch, Ezio Bartocci, Junxing Yang, Ashish Tiwari, Scott A. Smolka, Radu Grosu

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish
Title of host publicationTools 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
PublisherSpringer
Pages286-302
Number of pages17
Volume10206
ISBN (Print)9783662545799
DOIs
Publication statusE-pub ahead of print - 31 Mar 2017
Event23rd 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, Sweden
Duration: 22 Apr 201729 Apr 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10206 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference23rd 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
CountrySweden
City Uppsala
Period22/04/1729/04/17

Fingerprint

Horizon
Synthesis
Birds
Approximation algorithms
Lyapunov functions
Flock
Particle swarm optimization (PSO)
Markov Decision Process
Costs
Energy conservation
Controllers
Topological Equivalence
Topological Relations
Flocking
Particle Swarm
Energy Conservation
Optimal Policy
Equivalence relation
Lyapunov Function
Particle Swarm Optimization

Bibliographical note

© Springer-Verlag GmbH Germany 2017. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-54580-5_17

Cite this

Lukina, A., Esterle, L., Hirsch, C., Bartocci, E., Yang, J., Tiwari, A., ... Grosu, R. (2017). ARES: Adaptive receding-horizon synthesis of optimal plans. In Tools 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 (Vol. 10206, pp. 286-302). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10206 LNCS). Springer. https://doi.org/10.1007/978-3-662-54580-5_17
Lukina, Anna ; Esterle, Lukas ; Hirsch, Christian ; Bartocci, Ezio ; Yang, Junxing ; Tiwari, Ashish ; Smolka, Scott A. ; Grosu, Radu. / ARES : Adaptive receding-horizon synthesis of optimal plans. Tools 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. Vol. 10206 Springer, 2017. pp. 286-302 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{292296a469f8474fbaa120c2331b1d0c,
title = "ARES: Adaptive receding-horizon synthesis of optimal plans",
abstract = "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.",
author = "Anna Lukina and Lukas Esterle and Christian Hirsch and Ezio Bartocci and Junxing Yang and Ashish Tiwari and Smolka, {Scott A.} and Radu Grosu",
note = "{\circledC} Springer-Verlag GmbH Germany 2017. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-54580-5_17",
year = "2017",
month = "3",
day = "31",
doi = "10.1007/978-3-662-54580-5_17",
language = "English",
isbn = "9783662545799",
volume = "10206",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "286--302",
booktitle = "Tools 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",
address = "Germany",

}

Lukina, A, Esterle, L, Hirsch, C, Bartocci, E, Yang, J, Tiwari, A, Smolka, SA & Grosu, R 2017, ARES: Adaptive receding-horizon synthesis of optimal plans. in Tools 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. vol. 10206, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10206 LNCS, Springer, pp. 286-302, 23rd 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, Sweden, 22/04/17. https://doi.org/10.1007/978-3-662-54580-5_17

ARES : Adaptive receding-horizon synthesis of optimal plans. / Lukina, Anna; Esterle, Lukas; Hirsch, Christian; Bartocci, Ezio; Yang, Junxing; Tiwari, Ashish; Smolka, Scott A.; Grosu, Radu.

Tools 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. Vol. 10206 Springer, 2017. p. 286-302 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10206 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - ARES

T2 - Adaptive receding-horizon synthesis of optimal plans

AU - Lukina, Anna

AU - Esterle, Lukas

AU - Hirsch, Christian

AU - Bartocci, Ezio

AU - Yang, Junxing

AU - Tiwari, Ashish

AU - Smolka, Scott A.

AU - Grosu, Radu

N1 - © Springer-Verlag GmbH Germany 2017. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-54580-5_17

PY - 2017/3/31

Y1 - 2017/3/31

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85017518302&partnerID=8YFLogxK

UR - https://link.springer.com/chapter/10.1007%2F978-3-662-54580-5_17

U2 - 10.1007/978-3-662-54580-5_17

DO - 10.1007/978-3-662-54580-5_17

M3 - Conference contribution

AN - SCOPUS:85017518302

SN - 9783662545799

VL - 10206

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 286

EP - 302

BT - Tools 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

PB - Springer

ER -

Lukina A, Esterle L, Hirsch C, Bartocci E, Yang J, Tiwari A et al. ARES: Adaptive receding-horizon synthesis of optimal plans. In Tools 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. Vol. 10206. Springer. 2017. p. 286-302. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-662-54580-5_17