Informed Steiner Trees: Sampling and Pruning for Multi-Goal Path Finding in High Dimensions
We interleave sampling based motion planning methods with pruning ideas from minimum spanning tree algorithms to develop a new approach for solving a Multi-Goal Path Finding (MGPF) problem in high dimensional spaces. The approach alternates between sampling points from selected regions in the search space and de-emphasizing regions that may not lead to good solutions for MGPF. Our approach provides an asymptotic, 2-approximation guarantee for MGPF. We also present extensive numerical results to illustrate the advantages of our proposed approach over uniform sampling in terms of the quality of the solutions found and computation speed.
Code (0)
등록된 구현이 없습니다.
Tasks
Motion PlanningMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
A Hierarchical Heuristic for Clustered Steiner Trees in the Plane with Obstacles
Euclidean Steiner trees are relevant to model minimal networks in real-world applications ubiquitously. In this paper, we study the feasibility of a hierarchical approach embedded with bundling operations to compute mult…
Randomized HyperSteiner: A Stochastic Delaunay Triangulation Heuristic for the Hyperbolic Steiner Minimal Tree
We study the problem of constructing Steiner Minimal Trees (SMTs) in hyperbolic space. Exact SMT computation is NP-hard, and existing hyperbolic heuristics such as HyperSteiner are deterministic and often get trapped in …
NeuroSteiner: A Graph Transformer for Wirelength Estimation
A core objective of physical design is to minimize wirelength (WL) when placing chip components on a canvas. Computing the minimal WL of a placement requires finding rectilinear Steiner minimum trees (RSMTs), an NP-hard …
NavigateNearly Optimal Steiner Trees using Graph Neural Network Assisted Monte Carlo Tree Search
Graph neural networks are useful for learning problems, as well as for combinatorial and graph problems such as the Subgraph Isomorphism Problem and the Traveling Salesman Problem. We describe an approach for computing S…
Graph Neural NetworkTraveling Salesman ProblemComputing Steiner Trees using Graph Neural Networks
Graph neural networks have been successful in many learning problems and real-world applications. A recent line of research explores the power of graph neural networks to solve combinatorial and graph algorithmic problem…
Graph AttentionGraph GenerationGraph LearningSteiner Tree Problem+1