Width Based Planning
Width
Width Based Planning searches for solutions through a general measure of state novelty. When the dynamics of the problem are given through simulator engines such as the Atari games (ALE), GVGAI, or complex robotic and UaV flight simulators, novelty exploration yields state-of-the-art performance compared to known alternatives such as MCTS. Novelty exploration can be combined as well with the exploitation of goal-based heuristics within a general Best First Width Search. BFWS can solve efficiently classical planning problems even when the action model is hidden, opening exciting opportunities to model beyond declarative action representations.
Talks:
-
Tractable novelty exploration over Continuous and Discrete Sequential Decision Problems, School of Computing and information Systems Seminar, The University of Melbourne, September 2021
-
Width-Based Algorithms for Common Problems in Control, Planning and Reinforcement Learning, Early Career Spotlight at IJCAI 2021.
Papers:
(Disclaimer: this is not a comprehensive list, please get in touch to add relevant work that has been missed)
A position paper ` Width-Based Algorithms for Common Problems in Control, Planning and Reinforcement Learning’ was presented as part of the Early Career Spotlight at IJCAI 2021.
Table of Contents
- Classical Planning over STRIPS/PDDL
- Classical Planning over Simulators
- Continous State Simulators
- Planning and Learning
- Planning over Factored Simulators in Functional STRIPS
- MDP over Simulators
- Multi Agent (Descentralisd & Privacy Preserving) Planning
Classical Planning over PDDL
-
Classical Width Definition, Iterative Width (IW), Serialized IW (SIW), SIW+, and DFS+ algorithms
-
Best First Width Search (BFWS)
- N. Lipovetzky and H. Geffner, AAAI17
- Polynomial BFWS planner N. Lipovetzky and H. Geffner, ICAPS17
- BFWS and quantified heuristic novelty measures M. Katz, N. Lipovetzky, D. Moshkovich, A. Tuisov, ICAPS17
-
Approximate Novelty computation
-
Action Novelty
-
Novelty Decompositions
Classical Planning over Simulators
- IW over Atari Simulator (ALE)
Continous State Simulators
- Features for Continuous-State Domains. Competitive with DRL and LQR on control problems over gym.openai simulator
Pleanning and Learning
- IW and Learnt Policies M Junyent, A Jonsson, V Gómez, ICAPS19
- Hierarchical Learning M Junyent, A Jonsson, V Gómez, ICAPS21
- Learning symbolic representation with VAE A Dittadi, FK Drachmann, T Bolander
Planning over Factored Simulators in Functional STRIPS
Factored simulators accept finite domain variables, and mixed Declarative and Programatic (simulated) dynamics
- BFWS with simulators and Functional STRIPS (FSTRIPS) - G. Francès, M. Ramirez, N. Lipovetzky, and H. Geffner, IJCAI17
- Task and Motion Planning - J. Ferrer-Mestres, G. Francès, and H. Geffner, ARXIV17
- UaV Hybrid Control - M. Ramirez, M. Papasimeon, N. Lipovetzky, L. Benke, T. Miller, A. Pearce, E. Scala, M. Zamani, AAMAS18
- BFWS online POMDP for Transparent Planning - A. MacNally, N. Lipovetzky, M. Ramirez, A. Pearce, AAMAS18
MDP over Simulators
- IW over General Videogame Competition (GVGAI) - T. Geffner and H. Geffner, AAIDE15
Multi Agent Descentralised and Privacy Preserving Planning
- Descentralised Best First Width Search (MA-BFWS) AE Gerevini, N Lipovetzky, F Percassi, A Saetti, I Serina, ICAPS2019
- Novelty Communication filtering for Strong Privacy Preserving Planning AE Gerevini, N Lipovetzky, N Peli, F Percassi, A Saetti, I Serina, SoCS2019
- Width-based search for multi agent privacy-preserving planning AE Gerevini, N Lipovetzky, F Percassi, A Saetti, I Serina, AIJ 2023