S&Reg v2: a probabilistically complete sampling-based planner to solve multi-goal path finding problem via multi-task learning networks

被引:0
作者
Huang, Yuan [1 ]
Zhang, Yilin [2 ]
机构
[1] Wenzhou Business Coll, Coll Informat & Technol, Wenzhou, Peoples R China
[2] Waseda Univ, Grad Sch Informat Prod & Syst, Kitakyushu, Japan
关键词
Multi-goal path finding problem; physical traveling salesman problem; neural networks; Rapidly-exploring Random Tree (RRT);
D O I
10.1080/01691864.2024.2407130
中图分类号
TP24 [机器人技术];
学科分类号
080202 ; 1405 ;
摘要
In this paper, we present a variant of our previous research on multi-goal path finding problem, focusing on finding a feasible and closed path to visit a sequence of goals in an environment with obstacles. The newly proposed method, Segmentation & Regression v2 (S&Reg v2), employs multi-task learning networks to generate regions and estimates of lengths of local paths between pairwise goals. Importantly, the estimates are performed as weights for a complete graph to compute the visiting sequence. Subsequently, the path-finding process is executed following the sequence, and the predicted region works as a sampling domain to enhance the search speed. A hybrid sampler is designed by combining a uniform domain with the region domain, ensuring successful samples, even if the region is disconnected. Besides, a selection rule is introduced to balance the sampling domain during different searching stages. A proof of probabilistic completeness of the S&Reg v2 method is given. Simulations verify the superior performance of the S&Reg v2 method, demonstrating a reduction in calculation time ranging from 3.9% to 13.0%. Furthermore, a practical scenario validates the reliability of S&Reg v2, achieving a 15.0% improvement in success rate and a 9.7% reduction in calculation time.
引用
收藏
页码:1668 / 1678
页数:11
相关论文
共 27 条
[1]  
Ali HA., 2008, PROC WRLD ACAD SCI E, V2, P123
[2]   Autonomous tracking and landing of an unmanned aerial vehicle on a ground vehicle in rough terrain [J].
Aoki, Nobuaki ;
Ishigami, Genya .
ADVANCED ROBOTICS, 2023, 37 (05) :344-355
[3]  
Applegate David, 2006, Concorde tsp solver
[4]  
Chandak N., 2022, P INT S COMBINATORIA, V15, P258
[5]  
Devaurs D, 2014, IEEE INT C INT ROBOT, P2991, DOI 10.1109/IROS.2014.6942975
[6]  
Dimitrovski F., 2019, ELKAI
[7]   Data collection path planning with spatially correlated measurements using growing self-organizing array [J].
Faigl, Jan .
APPLIED SOFT COMPUTING, 2019, 75 :130-147
[8]   Autonomous Data Collection Using a Self-Organizing Map [J].
Faigl, Jan ;
Hollinger, Geoffrey A. .
IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS, 2018, 29 (05) :1703-1715
[9]   Generative Adversarial Networks [J].
Goodfellow, Ian ;
Pouget-Abadie, Jean ;
Mirza, Mehdi ;
Xu, Bing ;
Warde-Farley, David ;
Ozair, Sherjil ;
Courville, Aaron ;
Bengio, Yoshua .
COMMUNICATIONS OF THE ACM, 2020, 63 (11) :139-144
[10]   An effective implementation of the Lin-Kernighan traveling salesman heuristic [J].
Helsgaun, K .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 126 (01) :106-130