Progression Heuristics for Planning with Probabilistic LTL Constraints

02/02/2021

Progression Heuristics for Planning with Probabilistic LTL Constraints

Ian Mallett, Sylvie Thiebaux, Felipe Trevizan

Keywords:

Abstract Paper Similar Papers

Abstract: Probabilistic planning subject to multi-objective probabilistic temporal logic (PLTL) constraints models the problem of computing safe and robust behaviours for agents in stochastic environments. We present novel admissible heuristics to guide the search for cost-optimal policies for these problems. These heuristics project and decompose LTL formulae obtained by progression to estimate the probability that an extension of a partial policy satisfies the constraints. Their computation with linear programming is integrated with the recent PLTL-dual heuristic search algorithm, enabling more aggressive pruning of regions violating the constraints. Our experiments show that they further widen the scalability gap between heuristic search and verification approaches to these planning problems.

The video of this talk cannot be embedded. You can watch it here:

https://slideslive.com/38948504

(Link will open in new window)

0

0

0

0

Share

This is an embedded video. Talk and the respective paper are published at AAAI 2021 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment

no comments yet

Similar Papers

06/12/2021

Heuristic-Guided Reinforcement Learning

Ching-An Cheng, Andrey Kolobov, Adith Swaminathan

Keywords Paper

theory, reinforcement learning and planning

0

0

0

0

8:39

26/04/2020

Meta-Learning Acquisition Functions for Transfer Learning in Bayesian Optimization

Michael Volpp, Lukas P. Fröhlich, Kirsten Fischer and
Andreas Doerr, Stefan Falkner, Frank Hutter, Christian Daniel

Keywords Paper

Transfer Learning, Meta Learning, Bayesian Optimization, Reinforcement Learning

0

0

0

0

5:05

06/12/2021

Automated Dynamic Mechanism Design

Hanrui Zhang, Vincent Conitzer

Keywords Paper

0

0

0

0

14:35

19/08/2021

On Guaranteed Optimal Robust Explanations for NLP Models

Emanuele La Malfa, Rhiannon Michelmore, Agnieszka M. Zbrzezny and
Nicola Paoletti, Marta Kwiatkowska

Keywords Paper

Machine Learning, Adversarial Machine Learning, Explainable/Interpretable Machine Learning, Sentiment Analysis and Text Mining

0

0

0

0

14:52

13/04/2021

Adversarially robust estimate and risk analysis in linear regression

Yue Xing, Ruizhi Zhang, Guang Cheng

Keywords Paper

0

0

0

0

3:03

18/07/2021

CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee

Tengyu Xu, Yingbin LIANG, Guanghui Lan

Keywords Paper

Theory, RL, Decisions and Control Theory

0

0

0

0

5:15

06/12/2020

Promoting Stochasticity for Expressive Policies via a Simple and Efficient Regularization Method

Qi Zhou, Yufei Kuang, Zherui Qiu and
Houqiang Li, Jie Wang

Keywords Paper

0

0

0

0

3:10

03/05/2021

On the role of planning in model-based deep reinforcement learning

Jessica Hamrick, Abram Friesen, Feryal Behbahani and
Arthur Guez, Fabio Viola, Sims Witherspoon, Thomas Anthony, Lars Buesing, Petar Veličković, Theo Weber

Keywords Paper

planning, MuZero, model-based RL

0

0

0

0

5:15

26/08/2020

Discrete Action On-Policy Learning with Action-Value Critic

Yuguang Yue, Yunhao Tang, Mingzhang Yin, Mingyuan Zhou

Keywords Paper

0

0

0

0

14:23

06/12/2021

Towards Robust Bisimulation Metric Learning

Mete Kemertas, Tristan Aumentado-Armstrong

Keywords Paper

reinforcement learning and planning, robustness, representation learning

0

0

0

0

12:24

06/12/2021

Stateful Strategic Regression

Keegan Harris, Hoda Heidari, Steven Wu

Keywords Paper

optimization

0

0

0

0

14:02

06/12/2021

Taming Communication and Sample Complexities in Decentralized Policy Evaluation for Cooperative Multi-Agent Reinforcement Learning

Xin Zhang, Zhuqing Liu, Jia Liu and
Zhengyuan Zhu, Songtao Lu

Keywords Paper

theory, optimization, reinforcement learning and planning

0

0

0

0

14:54

26/04/2020

Multi-Agent Interactions Modeling with Correlated Policies

Minghuan Liu, Ming Zhou, Weinan Zhang and
Yuzheng Zhuang, Jun Wang, Wulong Liu, Yong Yu

Keywords Paper

Multi-agent reinforcement learning, Imitation learning

0

0

0

0

4:33

06/12/2021

Is Bang-Bang Control All You Need? Solving Continuous Control with Bernoulli Policies

Tim Seyde, Igor Gilitschenski, Wilko Schwarting and
Bartolomeo Stellato, Martin Riedmiller, Markus Wulfmeier, Daniela Rus

Keywords Paper

reinforcement learning and planning

0

0

0

0

6:48

06/12/2021

Structured Dropout Variational Inference for Bayesian Neural Networks

Son Nguyen, Duong Nguyen, Khai Nguyen and
Khoat Than, Hung Bui, Nhat Ho

Keywords Paper

deep learning, generative model

0

0

0

0

11:28

16/11/2020

Motion Planner Augmented Reinforcement Learning for Robot Manipulation in Obstructed Environments

Jun Yamada, Youngwoon Lee, Gautam Salhotra and
Karl Pertsch, Max Pflueger, Gaurav Sukhatme, Joseph Lim, Peter Englert

Keywords Paper

0

0

0

0

4:59

03/05/2021

C-Learning: Horizon-Aware Cumulative Accessibility Estimation

Panteha Naderian, Gabriel Loaiza-Ganem, Harry Braviner and
Anthony Caterini, Jesse C Cresswell, Tong Li, Animesh Garg

Keywords Paper

reinforcement learning, goal reaching, Q-learning

0

0

0

0

4:49

19/08/2021

Policy Learning with Constraints in Model-free Reinforcement Learning: A Survey

Yongshuai Liu, Avishai Halev, Xin Liu

Keywords Paper

Machine learning, General, General, General

0

0

0

0

15:25

26/08/2020

Finite-Time Analysis of Decentralized Temporal-Difference Learning with Linear Function Approximation

Jun Sun, Gang Wang, Georgios B. Giannakis and
Qinmin Yang, Zaiyue Yang

Keywords Paper

0

0

0

0

17:07

12/07/2020

Structured Policy Iteration for Linear Quadratic Regulator

Youngsuk Park, Ryan Rossi, Zheng Wen and
Gang Wu, Handong Zhao

Keywords Paper

Reinforcement Learning - General

0

0

0

0

16:08

12/07/2020

Randomized Block-Diagonal Preconditioning for Parallel Learning

Celestine Mendler-Dünner, Aurelien Lucchi

Keywords Paper

Optimization - Large Scale, Parallel and Distributed

0

0

0

0

12:57

18/07/2021

Provably Efficient Algorithms for Multi-Objective Competitive RL

Tiancheng Yu, Yi Tian, Jingzhao Zhang, Suvrit Sra

Keywords Paper

Theory, RL, Decisions and Control Theory

0

0

0

0

17:04

06/12/2021

Successor Feature Landmarks for Long-Horizon Goal-Conditioned Reinforcement Learning

Christopher Hoang, Sungryull Sohn, Jongwook Choi and
Wilka Carvalho, Honglak Lee

Keywords Paper

reinforcement learning and planning, graph learning

0

0

0

0

14:57

18/07/2021

Explaining Time Series Predictions with Dynamic Masks

Jonathan Crabbé, Mihaela van der Schaar

Keywords Paper

Social Aspects of Machine Learning, Fairness, Accountability, and Transparency

0

0

0

0

5:17

06/12/2021

Generalized Proximal Policy Optimization with Sample Reuse

James Queeney, Yannis Paschalidis, Christos G Cassandras

Keywords Paper

optimization, reinforcement learning and planning

0

0

0

0

13:45

19/10/2020

Autonomous predictive modeling via reinforcement learning

Udayan Khurana, Horst Samulowitz

Keywords Paper

reinforcement learning, data science automation, automated machine learning

0

0

0

0

4:21

06/12/2021

Design of Experiments for Stochastic Contextual Linear Bandits

Andrea Zanette, Kefan Dong, Jonathan N Lee, Emma Brunskill

Keywords Paper

reinforcement learning and planning, bandits

0

0

0

0

13:58

18/07/2021

Provably Correct Optimization and Exploration with Non-linear Policies

Fei Feng, Wotao Yin, Alekh Agarwal, Lin Yang

Keywords Paper

Deep Learning, Adversarial Networks, Applications, Fairness, Accountability, and Transparency, Theory, RL, Decisions and Control Theory

0

0

0

0

5:03

19/08/2021

Variational Model-based Policy Optimization

Yinlam Chow, Brandon Cui, Moonkyung Ryu, Mohammad Ghavamzadeh

Keywords Paper

Machine Learning, Reinforcement Learning

0

0

0

0

15:31

18/07/2021

Combining Pessimism with Optimism for Robust and Efficient Model-Based Deep Reinforcement Learning

Sebastian Curi, Ilija Bogunovic, Andreas Krause

Keywords Paper

Reinforcement Learning and Planning

0

0

0

0

4:41

06/12/2021

Neural Algorithmic Reasoners are Implicit Planners

Andreea-Ioana Deac, Petar Veličković, Ognjen Milinkovic and
Pierre-Luc Bacon, Jian Tang, Mladen Nikolic

Keywords Paper

deep learning, reinforcement learning and planning, self-supervised learning, generative model, graph learning

0

0

0

0

13:10

06/12/2021

Multi-Agent Reinforcement Learning in Stochastic Networked Systems

Yiheng Lin, Guannan Qu, Longbo Huang, Adam Wierman

Keywords Paper

reinforcement learning and planning, graph learning

0

0

0

0

11:20

06/12/2021

On the Convergence Theory of Debiased Model-Agnostic Meta-Reinforcement Learning

Alireza Fallah, Kristian Georgiev, Aryan Mokhtari, Asuman Ozdaglar

Keywords Paper

theory, optimization, reinforcement learning and planning, meta learning

0

1

1

0

12:25

06/12/2021

Local policy search with Bayesian optimization

Sarah Müller, Alexander von Rohr, Sebastian Trimpe

Keywords Paper

theory, optimization, reinforcement learning and planning, active learning

0

0

0

0

11:42

06/12/2021

Beyond BatchNorm: Towards a Unified Understanding of Normalization in Deep Learning

Ekdeep S Lubana, Robert Dick, Hidenori Tanaka

Keywords Paper

deep learning

0

0

0

0

8:28

12/07/2020

A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton

Risheng Liu, Pan Mu, Xiaoming Yuan and
Shangzhi Zeng, Jin Zhang

Keywords Paper

Optimization - Non-convex

0

0

0

0

13:51

03/05/2021

Trusted Multi-View Classification

Zongbo Han, Changqing Zhang, Huazhu FU, Joey T Zhou

Keywords Paper

Uncertainty Machine Learning, Multi-View Learning, Multi-Modal Learning

0

0

0

0

4:33

12/07/2020

Flexible and Efficient Long-Range Planning Through Curious Exploration

Aidan Curtis, Minjian Xin, Dilip Arumugam and
Kevin Feigelis, Daniel Yamins

Keywords Paper

Reinforcement Learning - General

0

0

0

0

16:25

06/12/2020

Interior Point Solving for LP-based prediction+optimisation

Jayanta Mandi, Tias Guns

Keywords Paper

0

0

0

1

3:28

02/02/2021

Dynamic Automaton-Guided Reward Shaping for Monte Carlo Tree Search

Alvaro Velasquez, Brett Bissey, Lior Barak and
Andre Beckus, Ismail Alkhouri, Daniel Melcer, George Atia

Keywords Paper

0

0

0

0

18:52