Multi-Objective Path-Based D* Lite

• URL: http://arxiv.org/abs/2108.00710v1
• Date: Mon, 2 Aug 2021 08:24:32 GMT
• Title: Multi-Objective Path-Based D* Lite
• Authors: Zhongqiang Ren, Sivakumar Rathinam and Howie Choset
• Abstract summary: Incremental graph search algorithms, such as D* Lite, reuse previous search efforts to speed up subsequent similar path planning tasks. This article presents a new multi-objective incremental search algorithm called Multi-Objective Path-Based D* Lite (MOPBD*) Numerical results show that MOPBD* is more efficient than search from scratch and runs an order of magnitude faster than existing incremental method for path planning.
• Score: 10.354181009277623
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Incremental graph search algorithms, such as D* Lite, reuse previous search efforts to speed up subsequent similar path planning tasks. These algorithms have demonstrated their efficiency in comparison with search from scratch, and have been leveraged in many applications such as navigation in unknown terrain. On the other hand, path planning typically involves optimizing multiple conflicting objectives simultaneously, such as travel risk, arrival time, etc. Multi-objective path planning is challenging as the number of "Pareto-optimal" solutions can grow exponentially with respect to the size of the graph, which makes it computationally burdensome to plan from scratch each time when similar planning tasks needs to be solved. This article presents a new multi-objective incremental search algorithm called Multi-Objective Path-Based D* Lite (MOPBD*) which reuses previous search efforts to speed up subsequent planning tasks while optimizing multiple objectives. Numerical results show that MOPBD* is more efficient than search from scratch and runs an order of magnitude faster than existing incremental method for multi-objective path planning.

Related papers

• LLM-A*: Large Language Model Enhanced Incremental Heuristic Search on Path Planning [91.95362946266577]
  Path planning is a fundamental scientific problem in robotics and autonomous navigation. Traditional algorithms like A* and its variants are capable of ensuring path validity but suffer from significant computational and memory inefficiencies as the state space grows. We propose a new LLM based route planning method that synergistically combines the precise pathfinding capabilities of A* with the global reasoning capability of LLMs. This hybrid approach aims to enhance pathfinding efficiency in terms of time and space complexity while maintaining the integrity of path validity, especially in large-scale scenarios.
  arXiv  Detail & Related papers  (2024-06-20T01:24:30Z)
• Tree-of-Mixed-Thought: Combining Fast and Slow Thinking for Multi-hop Visual Reasoning [16.495754104540605]
  Large language models (LLMs) can generate code-like plans for complex inference tasks such as visual reasoning. We propose a hierarchical plan-searching algorithm that integrates the one-stop reasoning (fast) and the Tree-of-thought (slow)
  arXiv  Detail & Related papers  (2023-08-18T16:21:40Z)
• Enhanced Multi-Objective A* with Partial Expansion [22.45142249108214]
  Multi-Objective Shortest Path Problem (MO-SPP), typically posed on a graph, determines a set of paths while optimizing multiple objectives. To address this problem, several Multi-Objective A* (MOA*) algorithms were recently developed to quickly compute solutions with quality guarantees. This work thus aims at reducing the high memory consumption of MOA* with little increase in the runtime.
  arXiv  Detail & Related papers  (2022-12-06T05:48:11Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  We present the first efficient scalable and general framework that can directly search on the tasks of interest. Inspired by the innate tree structure of the underlying math expressions, we re-arrange the spaces into a super-tree. We adopt an adaptation of the Monte Carlo method to tree search, equipped with rejection sampling and equivalent- form detection.
  arXiv  Detail & Related papers  (2022-09-27T17:51:31Z)
• TaSPM: Targeted Sequential Pattern Mining [53.234101208024335]
  We propose a generic framework namely TaSPM, based on the fast CM-SPAM algorithm. We also propose several pruning strategies to reduce meaningless operations in mining processes. Experiments show that the novel targeted mining algorithm TaSPM can achieve faster running time and less memory consumption.
  arXiv  Detail & Related papers  (2022-02-26T17:49:47Z)
• C-Planning: An Automatic Curriculum for Learning Goal-Reaching Tasks [133.40619754674066]
  Goal-conditioned reinforcement learning can solve tasks in a wide range of domains, including navigation and manipulation. We propose the distant goal-reaching task by using search at training time to automatically generate intermediate states. E-step corresponds to planning an optimal sequence of waypoints using graph search, while the M-step aims to learn a goal-conditioned policy to reach those waypoints.
  arXiv  Detail & Related papers  (2021-10-22T22:05:31Z)
• PathBench: A Benchmarking Platform for Classical and Learned Path Planning Algorithms [59.3879573040863]
  Path planning is a key component in mobile robotics. Few attempts have been made to benchmark the algorithms holistically or unify their interface. This paper presents PathBench, a platform for developing, visualizing, training, testing, and benchmarking of existing and future path planning algorithms.
  arXiv  Detail & Related papers  (2021-05-04T21:48:18Z)
• Subdimensional Expansion for Multi-objective Multi-agent Path Finding [10.354181009277623]
  Multi-agent path planners typically determine a path that optimize a single objective, such as path length. Many applications, however, may require multiple objectives, say time-to-completion and fuel use, to be simultaneously optimized in the planning process. This paper presents an approach that bypasses this so-called curse of dimensionality by leveraging our prior multi-agent work with a framework called subdimensional expansion.
  arXiv  Detail & Related papers  (2021-02-02T06:58:28Z)
• 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)
• Performance Improvement of Path Planning algorithms with Deep Learning Encoder Model [1.1995939891389429]
  Convolutional Neural Network (CNN) was used to overcome this situation. This paper analyzes in-depth the performance to eliminate the useless paths using this CNN model.
  arXiv  Detail & Related papers  (2020-08-05T17:34:31Z)
• 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)

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.