Heuristic Search for Multi-Objective Probabilistic Planning
- URL: http://arxiv.org/abs/2303.14363v1
- Date: Sat, 25 Mar 2023 05:18:22 GMT
- Title: Heuristic Search for Multi-Objective Probabilistic Planning
- Authors: Dillon Chen, Felipe Trevizan, Sylvie Thi\'ebaux
- Abstract summary: Heuristic search is a powerful approach that has successfully been applied to a broad class of planning problems.
Here, we extend the reach of search to a more class of problems, namely multi-objective shortest paths (MOSSPs)
We design new search algorithms MOLAO* and MOLRTDP, which extend well-known SSP algorithms to the multi-objective problem.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Heuristic search is a powerful approach that has successfully been applied to
a broad class of planning problems, including classical planning,
multi-objective planning, and probabilistic planning modelled as a stochastic
shortest path (SSP) problem. Here, we extend the reach of heuristic search to a
more expressive class of problems, namely multi-objective stochastic shortest
paths (MOSSPs), which require computing a coverage set of non-dominated
policies. We design new heuristic search algorithms MOLAO* and MOLRTDP, which
extend well-known SSP algorithms to the multi-objective case. We further
construct a spectrum of domain-independent heuristic functions differing in
their ability to take into account the stochastic and multi-objective features
of the problem to guide the search. Our experiments demonstrate the benefits of
these algorithms and the relative merits of the heuristics.
Related papers
- Learning Logic Specifications for Policy Guidance in POMDPs: an
Inductive Logic Programming Approach [57.788675205519986]
We learn high-quality traces from POMDP executions generated by any solver.
We exploit data- and time-efficient Indu Logic Programming (ILP) to generate interpretable belief-based policy specifications.
We show that learneds expressed in Answer Set Programming (ASP) yield performance superior to neural networks and similar to optimal handcrafted task-specifics within lower computational time.
arXiv Detail & Related papers (2024-02-29T15:36:01Z) - Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
Low-Rank Markov Decision Processes offer a simple, yet expressive framework for RL with function approximation.
Existing algorithms are either (1) computationally intractable, or (2) reliant upon restrictive statistical assumptions.
We propose the first provably sample-efficient algorithm for exploration in Low-Rank MDPs.
arXiv Detail & Related papers (2023-07-08T15:41:48Z) - Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
We present a new algorithm for a policy gradient in TMDPs by a simple extension of the proximal policy optimization (PPO) algorithm.
We demonstrate this on a real-world multiple-objective navigation problem with an arbitrary ordering of objectives both in simulation and on a real robot.
arXiv Detail & Related papers (2022-09-15T07:22:58Z) - Multi-objective Conflict-based Search Using Safe-interval Path Planning [10.354181009277623]
We present a new multi-objective conflict-based search (MO-CBS) approach that relies on a novel multi-objective safe interval path planning (MO-SIPP) algorithm for its low-level search.
We present extensive numerical results to show that there is an order of magnitude improvement in the average low level search time.
We also provide a case study to demonstrate the potential application of the proposed algorithms for construction site planning.
arXiv Detail & Related papers (2021-08-02T09:42:08Z) - A Unified View of Algorithms for Path Planning Using Probabilistic
Inference on Factor Graphs [2.4874504720536317]
This work looks at the specific recursions that arise from various cost functions that, although they may appear similar in scope, bear differences, at least when applied to typical path planning problems.
We show how this unified approach, presented both in probability space and in log space, provides a very general framework that includes the Sum-product, the Max-product, Dynamic programming and mixed Reward/Entropy criteria-based algorithms.
arXiv Detail & Related papers (2021-06-19T07:13:15Z) - Selection-Expansion: A Unifying Framework for Motion-Planning and
Diversity Search Algorithms [69.87173070473717]
We investigate the properties of two diversity search algorithms, the Novelty Search and the Goal Exploration Process algorithms.
The relation to MP algorithms reveals that the smoothness, or lack of smoothness of the mapping between the policy parameter space and the outcome space plays a key role in the search efficiency.
arXiv Detail & Related papers (2021-04-10T13:52:27Z) - Multi-objective Conflict-based Search for Multi-agent Path Finding [10.354181009277623]
Multi-objective path planners typically compute an ensemble of paths while optimizing a single objective, such as path length.
This article presents an approach named Multi-objective Conflict-based Search (MO-CBS) that bypasses this so-called curse of dimensionality.
arXiv Detail & Related papers (2021-01-11T10:42:38Z) - Learning Heuristic Selection with Dynamic Algorithm Configuration [44.91083687014879]
We show that dynamic algorithm configuration can be used for dynamic selection dynamics of a planning system.
We show that this approach generalizes over existing approaches and that it can exponentially improve performance of the domain search.
arXiv Detail & Related papers (2020-06-15T09:35:07Z) - Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal
Constraints [52.58352707495122]
We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination.
We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
arXiv Detail & Related papers (2020-05-27T01:10:41Z) - Flexible and Efficient Long-Range Planning Through Curious Exploration [13.260508939271764]
We show that the Curious Sample Planner can efficiently discover temporally-extended plans for solving a wide range of physically realistic 3D tasks.
In contrast, standard planning and learning methods often fail to solve these tasks at all or do so only with a huge and highly variable number of training samples.
arXiv Detail & Related papers (2020-04-22T21:47:29Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.