Informed Steiner Trees: Sampling and Pruning for Multi-Goal Path Finding in High Dimensions

被引：0

作者：

Chandak, Nikhil ^{[1
]}

Chour, Kenny ^{[2
]}

Rathinam, Sivakumar ^{[2
]}

Ravi, R. ^{[3
]}

机构：

[1] Int Inst Informat Technol, Gachibowli 500032, Telangana, India

[2] Texas A&M Univ, Dept Mech Engn, College Stn, TX 77845 USA

[3] Carnegie Mellon Univ, Tepper Sch Business, Pittsburgh, PA 15213 USA

来源：

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING | 2024年 / 21卷 / 04期

关键词：

Costs; Steiner trees; Planning; Space exploration; Self-organizing feature maps; Task analysis; Collision avoidance; Shortest path problem; steiner trees; approximation algorithms; motion planning; ALGORITHM; TASK;

D O I：

10.1109/TASE.2023.3307242

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：5048 / 5061

页数：14

共 50 条

[1]

Best G, 2016, 2016 IEEE/RSJ INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS 2016), P3164, DOI 10.1109/IROS.2016.7759489

[2]

Canny J., 1987, 28th Annual Symposium on Foundations of Computer Science (Cat. No.87CH2471-1), P49, DOI 10.1109/SFCS.1987.42

[3]

Chour K, 2021, Proceedings of the International Conference on Automated Planning and Scheduling, V31, P85, DOI 10.1609/icaps.v31i1.15950

[4]

Decroos T., 2015, P COMP PUBL ANN C GE, P1379

[5]

Devaurs D, 2014, IEEE INT C INT ROBOT, P2991, DOI 10.1109/IROS.2014.6942975

[6]

Edelkamp S., 2014, CURR MED RES OPIN, P1

[7] Surface Inspection via Hitting Sets and Multi-goal Motion Planning [J].

Edelkamp, Stefan ;

Secim, Baris Can ;

Plaku, Erion .

TOWARDS AUTONOMOUS ROBOTIC SYSTEMS (TAROS 2017), 2017, 10454 :134-149

[8] Three-dimensional coverage planning for an underwater inspection robot [J].

Englot, Brendan ;

Hover, Franz S. .

INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH, 2013, 32 (9-10) :1048-1073

[9] Fast Sequence Rejection for Multi-Goal Planning with Dubins Vehicle [J].

Faigl, Jan ;

Vana, Petr ;

Drchal, Jan .

2020 IEEE/RSJ INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS), 2020, :6773-6780

[10] Fast Heuristics for the 3-D Multi-Goal Path Planning Based on the Generalized Traveling Salesman Problem With Neighborhoods [J].

Faigl, Jan ;

Vana, Petr ;

Deckerova, Jindriska .

IEEE ROBOTICS AND AUTOMATION LETTERS, 2019, 4 (03) :2439-2446

← 1 2 3 4 5 →