Personal tools
You are here: Home Projects In-house Projects Sampling-Based Bottleneck Pathfinding with Applications to Fréchet Matching Sampling-Based Bottleneck Pathfinding With Applications To Fréchet Matching
« December 2018 »
December
SuMoTuWeThFrSa
1
2345678
9101112131415
16171819202122
23242526272829
3031
Log in


Forgot your password?
 

Sampling-Based Bottleneck Pathfinding With Applications To Fréchet Matching

Abstract

IROS
Simultaneous planning for multiple high-dimensional systems is a difficult,
 motivating challenge for this work.

We introduce a simple yet effective sampling-based planner that is tailored for bottleneck pathfinding: Given an implicitly-defined cost map M, which assigns to every point in space a real value, we wish to find a path connecting two given points, which minimizes the maximal value with respect to M. We demonstrate the capabilities of our algorithm, which we call bottleneck tree (BTT), on several challenging instances of the problem involving multiple agents, where it outperforms the state-of-the-art cost-map planning technique T-RRT*. In addition to its efficiency, BTT requires the tuning of only a single parameter: the number of samples. On the theoretical side, we study the asymptotic properties of our method and consider the special setting where the computed trajectories must be monotone in all coordinates. This constraint arises in cases where the problem involves the coordination of multiple agents that are restricted to forward motions along predefined paths.

Links

  • Kiril Solovey and Dan Halperin, “Efficient Sampling-Based Bottleneck Pathfinding over Cost Maps”
    International Conference on Intelligent Robots and Systems, 2017 (ESA 2016), to appear;
    IEEE Xplore
     [link]

Contacts

Kiril Solovey home icon contact
Dan Halperin http://acg.cs.tau.ac.il/danhalperin contact
Document Actions