A Multi-Heuristic Search-based Motion Planning for Automated Parking

• URL: http://arxiv.org/abs/2307.07857v1
• Date: Sat, 15 Jul 2023 17:33:06 GMT
• Title: A Multi-Heuristic Search-based Motion Planning for Automated Parking
• Authors: Bhargav Adabala, Zlatan Ajanovi\'c
• Abstract summary: In unstructured environments like parking lots or construction sites, it is challenging to achieve real-time planning. We are adopting a Multi-Heuristic Search approach, that enables the use of multiple functions and their individual advantages. The Multi-Heuristic A* algorithm is benchmarked against a very popular search-based algorithm, Hybrid A*.
• Score: 0.0
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: In unstructured environments like parking lots or construction sites, due to the large search-space and kinodynamic constraints of the vehicle, it is challenging to achieve real-time planning. Several state-of-the-art planners utilize heuristic search-based algorithms. However, they heavily rely on the quality of the single heuristic function, used to guide the search. Therefore, they are not capable to achieve reasonable computational performance, resulting in unnecessary delays in the response of the vehicle. In this work, we are adopting a Multi-Heuristic Search approach, that enables the use of multiple heuristic functions and their individual advantages to capture different complexities of a given search space. Based on our knowledge, this approach was not used previously for this problem. For this purpose, multiple admissible and non-admissible heuristic functions are defined, the original Multi-Heuristic A* Search was extended for bidirectional use and dealing with hybrid continuous-discrete search space, and a mechanism for adapting scale of motion primitives is introduced. To demonstrate the advantage, the Multi-Heuristic A* algorithm is benchmarked against a very popular heuristic search-based algorithm, Hybrid A*. The Multi-Heuristic A* algorithm outperformed baseline in both terms, computation efficiency and motion plan (path) quality.

Related papers

• Heuristic Search for Multi-Objective Probabilistic Planning [0.0]
  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.
  arXiv  Detail & Related papers  (2023-03-25T05:18:22Z)
• 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)
• A distributed, plug-n-play algorithm for multi-robot applications with a priori non-computable objective functions [2.2452191187045383]
  In multi-robot applications, the user-defined objectives of the mission can be cast as a general optimization problem. Standard gradient-descent-like algorithms are not applicable to these problems. We introduce a new algorithm that carefully designs each robot's subcost function, the optimization of which can accomplish the overall team objective.
  arXiv  Detail & Related papers  (2021-11-14T20:40:00Z)
• Model-based Decision Making with Imagination for Autonomous Parking [50.41076449007115]
  The proposed algorithm consists of three parts: an imaginative model for anticipating results before parking, an improved rapid-exploring random tree (RRT) and a path smoothing module. Our algorithm is based on a real kinematic vehicle model; which makes it more suitable for algorithm application on real autonomous cars. In order to evaluate the algorithm's effectiveness, we have compared our algorithm with traditional RRT, within three different parking scenarios.
  arXiv  Detail & Related papers  (2021-08-25T18:24:34Z)
• Prioritized SIPP for Multi-Agent Path Finding With Kinematic Constraints [0.0]
  Multi-Agent Path Finding (MAPF) is a long-standing problem in Robotics and Artificial Intelligence. We present a method that mitigates this issue to a certain extent.
  arXiv  Detail & Related papers  (2021-08-11T10:42:11Z)
• 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)
• AutoSpace: Neural Architecture Search with Less Human Interference [84.42680793945007]
  Current neural architecture search (NAS) algorithms still require expert knowledge and effort to design a search space for network construction. We propose a novel differentiable evolutionary framework named AutoSpace, which evolves the search space to an optimal one. With the learned search space, the performance of recent NAS algorithms can be improved significantly compared with using previously manually designed spaces.
  arXiv  Detail & Related papers  (2021-03-22T13:28:56Z)
• Policy-Guided Heuristic Search with Guarantees [31.323430201941378]
  Policy-guided Heuristic Search (PHS) is a novel search algorithm that uses both a function and a policy. PHS compares favorably with A*, Weighted A*, Greedy Best-First Search, LevinTS, and PUCT in terms of number of problems solved and search time.
  arXiv  Detail & Related papers  (2021-03-21T22:30:57Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• 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)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

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.