Online Two-Robot Coordination Algorithm for Searching in Streets with Limited

doi:10.3778/j.issn.1673-9418.1909007

Abstract

Abstract:

Searching for a target in an unknown environment is a basic task scenario of robots. It has a wide range of applications in real life. The related problem has received much attention in the study of computational geometry and robotics. This paper considers an online problem of searching in a street by two limited sensing robots. The street is defined as a simple polygon P with LR-visibility. Two robots equipped with limited sensing sensor start from the starting point s of P, and they can communicate with each other but have no previous knowledge of P. The goal of them is to search the ending point t of P with cooperation. The limited sensing sensor can only detect the discontinuities of the boundary of P in its visibility region, but cannot infer any other geometric information, such as distances or angles. Although the sensing capability is limited, the robot can provide low-cost solutions to challenging problems while achieving greater reliability in the face of uncertainties. Based on the geometry properties of the online searching model, this paper presents a 3-competitive online coordination algorithm and proves that it is optimal by showing a matching lower bound.

Key words: computational geometry, online coordination searching algorithm, competitive analysis, robot, limited sensing

摘要：

在未知环境中搜索一个目标，是机器人的基本任务场景之一，在现实中有着广泛的应用。相关问题在计算几何学科和机器人学科的研究中得到了广泛的关注。研究了一个双弱感知能力机器人在线协作搜索街道的问题。街道被定义为具有LR可视性的简单多边形P ，两个可相互通信的弱感知能力机器人从街道起点s出发，在预先不知道街道几何信息的前提下，协作完成街道终点t 的搜索。弱感知能力机器人携带的感应器仅能探测可视区域内街道边界的不连续情况，除此之外不能获取任何其他几何信息，如距离和角度。弱感知能力机器人虽然感知能力有限，却具有性价比高、面对不确定因素时可靠性强等优点。基于在线搜索模型的几何特征，提出了竞争比为3的在线协作搜索算法，并通过给出相匹配的竞争比下界，证明了算法的最优性。

关键词: 计算几何, 在线协作搜索算法, 竞争分析, 机器人, 弱感知

WEI Qi, LINWeida, WU Tong, REN Yonggong. Online Two-Robot Coordination Algorithm for Searching in Streets with Limited[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(9): 1571-1579.

魏琦，林韦达，吴彤，任永功. 双弱感知能力机器人在线协作街道搜索算法[J]. 计算机科学与探索, 2020, 14(9): 1571-1579.

References

[1] Foerster K T, Wattenhofer R. Lower and upper competitive bounds for online directed graph exploration[J]. Theoretical Computer Science, 2016, 655: 15-29.
[2] Angelopoulos S, Arsénio D, Dürr C. Infinite linear programming and online searching with turn cost[J]. Theoretical Computer Science, 2017, 670: 11-22.
[3] Ghosh S K, Klein R. Online algorithms for searching and exploration in the plane[J]. Computer Science Review, 2010, 4(4): 189-201.
[4] Chao Z Q, Wang F, Zhang C Q, et al. Research on the algorithm of measurement path planning for inner wall of air-intake pipe based on spraying robot system[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2017, 31(9): 1759018.
[5] Shao Q, Xu C C, Zhu Y. Multi-helicopter search and rescue route planning based on strategy optimization algorithm[J]. International Journal of Pattern Recognition and Artificial Intelligence, 2019, 33(1): 1950002.
[6] Klein R. Walking an unknown street with bounded detour[J]. Computational Geometry, 1991, 1: 325-351.
[7] Tseng L H, Heffernan P J, Lee D T. Two-guard walkability of simple polygons[J]. International Journal of Compu- tational Geometry and Applications, 1998, 8(1): 85-116.
[8] Ghosh S K, Saluja S. Optimal on-line algorithms for walking with minimum number of turns in unknown streets[J]. Computational Geometry, 1997, 8(5): 241-266.
[9] Icking C, Klein R, Langetepe E, et al. An optimal competitive strategy for walking in streets[J]. SIAM Journal on Computing, 2004, 33(2): 462-486.
[10] Tovar B, LaValle S M, Murrieta-Cid R. Optimal navigation and object finding without geometric maps or localization[C]//Proceedings of the 2003 IEEE International Conference on Robotics and Automation, Taipei, China, Sep 14-19, 2003. Piscataway: IEEE, 2003: 464-470.
[11] Lopez-Padilla R, Murrieta-Cid R, LaValle S M. Optimal gap navigation for a disc robot[C]//Proceedings of the 10th Workshop on the Algorithmic Foundations of Robotics, Cambridge, Jun 13-15, 2012. Berlin, Heidelberg: Springer, 2013: 123-138.
[12] Tabatabaei A, Ghodsi M. Walking in streets with minimal sensing[J]. Journal of Combinatorial Optimization, 2015, 30(2): 387-401.
[13] Baeza-Yates R A, Culberson J C, Rawlins G J E. Searching in the plane[J]. Information and Computation, 1993, 106(2): 234-252.
[14] Wei Q, Tan X H, Ren Y G. Walking an unknown street with limited sensing[J]. International Journal of Pattern Recog-nition and Artificial Intelligence, 2019, 33(13): 1959042.
[15] Marangoz S, Amasyal M F, Uslu E, et al. More scalable solution for multi-robot-multi-target assignment problem[J]. Robotics and Autonomous Systems, 2019, 113: 174-185.
[16] Juliá M, Gil A, Reinoso ó. A comparison of path planning strategies for autonomous exploration and mapping of unknown environments[J]. Autonomous Robots, 2012, 33(4): 427-444.
[17] Nieto-Granda C, Rogers III J G, Christensen H I. Coordination strategies for multi-robot exploration and mapping[J]. International Journal of Robotics Research, 2014, 33(4): 519-533.
[18] Czyzowicz J, G?sieniec L, Georgiou K, et al. The beachcombers, problem: walking and searching with mobile robots [J]. Theoretical Computer Science, 2015, 608: 201-218.
[19] Burgard W, Moors M, Stachniss C, et al. Coordinated multi-robot exploration[J]. IEEE Transactions on Robotics, 2005, 21(3): 376-386.
[20] Ortolf C, Schindelhauer C. Online multi-robot exploration of grid graphs with rectangular obstacles[C]//Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures, Pittsburgh, Jun 25-27, 2012. New York: ACM, 2012: 27-36.
[21] Sleator D D, Tarjan R E. Amortized efficiency of list update and paging rules[J]. Communications of the ACM, 1985, 28(2): 202-208.