Multi-objective Conflict-based Search Using Safe-interval Path Planning

• URL: http://arxiv.org/abs/2108.00745v1
• Date: Mon, 2 Aug 2021 09:42:08 GMT
• Title: Multi-objective Conflict-based Search Using Safe-interval Path Planning
• Authors: Zhongqiang Ren, Sivakumar Rathinam and Howie Choset
• Abstract summary: 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.
• Score: 10.354181009277623
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper addresses a generalization of the well known multi-agent path finding (MAPF) problem that optimizes multiple conflicting objectives simultaneously such as travel time and path risk. This generalization, referred to as multi-objective MAPF (MOMAPF), arises in several applications ranging from hazardous material transportation to construction site planning. In this paper, 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 first develop the MO-SIPP algorithm, show its properties and then embed it in MO-CBS. We present extensive numerical results to show that (1) there is an order of magnitude improvement in the average low level search time, and (2) a significant improvement in the success rates of finding the Pareto-optimal front can be obtained using the proposed approach in comparison with the state of the art. Finally, we also provide a case study to demonstrate the potential application of the proposed algorithms for construction site planning.

Related papers

• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
  In Multi-objective Reinforcement Learning (MORL) agents are tasked with optimising decision-making behaviours. We focus on the case of linear utility functions parameterised by weight vectors w. We introduce a method based on Upper Confidence Bound to efficiently search for the most promising weight vectors during different stages of the learning process.
  arXiv  Detail & Related papers  (2024-05-01T09:34:42Z)
• MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem [5.580214316179672]
  The MG-MAPF problem requires each agent to visit pre-assigned multiple goal points at least once without conflict. We propose the Multi-Goal Conflict-Based Search (MGCBS), which is based on Decoupling the goal Safe interval visiting order search and the Single-agent pathfinding. Our method can consistently obtain optimal results and execute up to 7 times faster than the state-of-the-art method in our evaluation.
  arXiv  Detail & Related papers  (2024-04-30T12:49:54Z)
• Ensembling Prioritized Hybrid Policies for Multi-agent Pathfinding [18.06081009550052]
  Multi-Agent Reinforcement Learning (MARL) based Multi-Agent Path Finding (MAPF) has recently gained attention due to its efficiency and scalability. Several MARL-MAPF methods choose to use communication to enrich the information one agent can perceive. We propose a new method, Ensembling Prioritized Hybrid Policies (EPH)
  arXiv  Detail & Related papers  (2024-03-12T11:47:12Z)
• 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)
• A Novel Long-term Iterative Mining Scheme for Video Salient Object Detection [54.53335983750033]
  Short-term methodology conflicts with the real mechanism of our visual system. This paper proposes a novel VSOD approach, which performs VSOD in a complete long-term way. The proposed approach outperforms almost all SOTA models on five widely used benchmark datasets.
  arXiv  Detail & Related papers  (2022-06-20T04:27:47Z)
• Recent Advances in Embedding Methods for Multi-Object Tracking: A Survey [71.10448142010422]
  Multi-object tracking (MOT) aims to associate target objects across video frames in order to obtain entire moving trajectories. Embedding methods play an essential role in object location estimation and temporal identity association in MOT. We first conduct a comprehensive overview with in-depth analysis for embedding methods in MOT from seven different perspectives.
  arXiv  Detail & Related papers  (2022-05-22T06:54:33Z)
• CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces [20.389416558418382]
  We propose a novel concept of roadmaps called cooperative timed roadmaps (CTRMs) CTRMs enable each agent to focus on its important locations around potential solution paths in a way that considers the behavior of other agents to avoid inter-agent collisions. We developed a machine-learning approach that learns a generative model from a collection of relevant problem instances and plausible solutions.
  arXiv  Detail & Related papers  (2022-01-24T05:43:59Z)
• A survey on multi-objective hyperparameter optimization algorithms for Machine Learning [62.997667081978825]
  This article presents a systematic survey of the literature published between 2014 and 2020 on multi-objective HPO algorithms. We distinguish between metaheuristic-based algorithms, metamodel-based algorithms, and approaches using a mixture of both. We also discuss the quality metrics used to compare multi-objective HPO procedures and present future research directions.
  arXiv  Detail & Related papers  (2021-11-23T10:22:30Z)
• Compilation-based Solvers for Multi-Agent Path Finding: a Survey, Discussion, and Future Opportunities [7.766921168069532]
  We show the lessons learned from past developments and current trends in the topic and discuss its wider impact. Two major approaches to optimal MAPF solving include (1) dedicated search-based methods, which solve MAPF directly, and (2) compilation-based methods that reduce a MAPF instance to an instance in a different well established formalism.
  arXiv  Detail & Related papers  (2021-04-23T20:13:12Z)
• 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)
• Provable Multi-Objective Reinforcement Learning with Generative Models [98.19879408649848]
  We study the problem of single policy MORL, which learns an optimal policy given the preference of objectives. Existing methods require strong assumptions such as exact knowledge of the multi-objective decision process. We propose a new algorithm called model-based envelop value (EVI) which generalizes the enveloped multi-objective $Q$-learning algorithm.
  arXiv  Detail & Related papers  (2020-11-19T22:35:31Z)

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.