Obstacle Aware Sampling for Path Planning

• URL: http://arxiv.org/abs/2203.04075v1
• Date: Tue, 8 Mar 2022 13:39:44 GMT
• Title: Obstacle Aware Sampling for Path Planning
• Authors: Murad Tukan and Alaa Maalouf and Dan Feldman and Roi Poranne
• Abstract summary: This paper aims to efficiently identify obstacles in a map and remove them from sampling space. We propose a pre-processing algorithm for space exploration that enables more efficient sampling. Experimental results confirm the effectiveness of our approach across multiple planners based Rapidly-exploring random trees.
• Score: 32.47559415297187
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many path planning algorithms are based on sampling the state space. While this approach is very simple, it can become costly when the obstacles are unknown, since samples hitting these obstacles are wasted. The goal of this paper is to efficiently identify obstacles in a map and remove them from the sampling space. To this end, we propose a pre-processing algorithm for space exploration that enables more efficient sampling. We show that it can boost the performance of other space sampling methods and path planners. Our approach is based on the fact that a convex obstacle can be approximated provably well by its minimum volume enclosing ellipsoid (MVEE), and a non-convex obstacle may be partitioned into convex shapes. Our main contribution is an algorithm that strategically finds a small sample, called the \emph{active-coreset}, that adaptively samples the space via membership-oracle such that the MVEE of the coreset approximates the MVEE of the obstacle. Experimental results confirm the effectiveness of our approach across multiple planners based on Rapidly-exploring random trees, showing significant improvement in terms of time and path length.

Related papers

• Learning a Fast Mixing Exogenous Block MDP using a Single Trajectory [87.62730694973696]
  STEEL is the first provably sample-efficient algorithm for learning the controllable dynamics of an Exogenous Block Markov Decision Process from a single trajectory. We prove that STEEL is correct and sample-efficient, and demonstrate STEEL on two toy problems.
  arXiv  Detail & Related papers  (2024-10-03T21:57:21Z)
• 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)
• CBAGAN-RRT: Convolutional Block Attention Generative Adversarial Network for Sampling-Based Path Planning [0.0]
  We propose a novel image-based learning algorithm (CBAGAN-RRT) using a Convolutional Block Attention Generative Adversarial Network. The probability distribution of the paths generated from our GAN model is used to guide the sampling process for the RRT algorithm. We train and test our network on the dataset generated by citezhang 2021 and demonstrate that our algorithm outperforms the previous state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2023-05-13T20:06:53Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Reducing Collision Checking for Sampling-Based Motion Planning Using Graph Neural Networks [10.698553177585973]
  We propose new learning-based methods for reducing collision checking to accelerate motion planning. We train graph neural networks (GNNs) that perform path exploration and path smoothing. Experimental results show that the learned components can significantly reduce collision checking and improve overall planning efficiency.
  arXiv  Detail & Related papers  (2022-10-17T09:02:04Z)
• PCB-RandNet: Rethinking Random Sampling for LIDAR Semantic Segmentation in Autonomous Driving Scene [15.516687293651795]
  We propose a new Polar Cylinder Balanced Random Sampling method for semantic segmentation of large-scale LiDAR point clouds. In addition, a sampling consistency loss is introduced to further improve the segmentation performance and reduce the model's variance under different sampling methods. Our approach produces excellent performance on both SemanticKITTI and SemanticPOSS benchmarks, achieving a 2.8% and 4.0% improvement, respectively.
  arXiv  Detail & Related papers  (2022-09-28T02:59:36Z)
• Generative Adversarial Network based Heuristics for Sampling-based Path Planning [34.368519009432426]
  We present a novel image-based path planning algorithm to overcome limitations of sampling-based path planning. Specifically, a generative adversarial network (GAN) is designed to take the environment map as the input without other preprocessing works. We conduct a number of simulation experiments to validate the effectiveness of the proposed method, and the results demonstrate that our method performs much better in terms of the quality of initial solution and the convergence speed to the optimal solution.
  arXiv  Detail & Related papers  (2020-12-07T07:29:57Z)
• AOT: Appearance Optimal Transport Based Identity Swapping for Forgery Detection [76.7063732501752]
  We provide a new identity swapping algorithm with large differences in appearance for face forgery detection. The appearance gaps mainly arise from the large discrepancies in illuminations and skin colors. A discriminator is introduced to distinguish the fake parts from a mix of real and fake image patches.
  arXiv  Detail & Related papers  (2020-11-05T06:17:04Z)
• Autonomous UAV Exploration of Dynamic Environments via Incremental Sampling and Probabilistic Roadmap [0.3867363075280543]
  We propose a novel dynamic exploration planner (DEP) for exploring unknown environments using incremental sampling and Probabilistic Roadmap (PRM) Our method safely explores dynamic environments and outperforms the benchmark planners in terms of exploration time, path length, and computational time.
  arXiv  Detail & Related papers  (2020-10-14T22:52:37Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Carath\'eodory Sampling for Stochastic Gradient Descent [79.55586575988292]
  We present an approach that is inspired by classical results of Tchakaloff and Carath'eodory about measure reduction. We adaptively select the descent steps where the measure reduction is carried out. We combine this with Block Coordinate Descent so that measure reduction can be done very cheaply.
  arXiv  Detail & Related papers  (2020-06-02T17:52:59Z)

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.