FNUG: Imperfect mazes traversal based on detecting and following the nearest-to-final-goal and unvisited gaps
FNUG: Imperfect mazes traversal based on detecting and following the nearest-to-final-goal and unvisited gaps
复制标题
FNUG：基于检测和跟踪最接近最终目标和未访问间隙的不完美迷宫遍历
DOI：
10.1109/lra.2022.3151393
复制
发表时间：
2022
影响因子：
5.2
通讯作者：
Muhammad Salam
中科院分区：
文献类型：
--
作者：
Zakir Ullah;Xiaopeng Chen;Siyuan Gou;Yang Xu;Muhammad Salam
迷宫遍历技术大致分为基于模型的迷宫遍历技术和基于传感器信息的迷宫遍历技术。在基于模型的技术中，配置空间以网格、势场或连接图的形式明确建模，而在基于传感器信息的技术中，所有控制决策都基于处理当前传感器的数据。没有可用的预模型的迷宫称为未知迷宫，而不完美的迷宫是有环路或闭路的迷宫。传统的基于信息的未知迷宫遍历技术大多基于试错法，既耗时又可能使机器人陷入无限循环或死胡同。针对上述问题，本文首次提出了一种基于间隙的不完美未知迷宫遍历方法，名为“跟随最近的最终目标和未访问间隙”（FNUG）。该算法计算效率高，并且能够通过重访检查处理循环和死胡同。该方法的主要部分是通过分析深度扫描找出机器人周围的间隙，以树的形式构建基于坐标系的拓扑图。然后根据机器人与最终目标位置的欧几里得距离，启发式选择机器人的未访问邻居间隙进行导航。与现有的基于传感器信息的方法相比，我们提出的算法不仅考虑了当前的传感器数据、机器人的形状和大小，还考虑了迄今为止访问的所有子目标。这是我们算法防止机器人陷入死胡同或陷入循环的关键因素。为了证明该算法的有效性，利用两轮差动移动机器人进行了仿真和物理实验。
Mazes traversal techniques are broadly classified into model-based and sensor information-based. In model-based techniques the configuration space is explicitly modeled in the form of a grid, potential field or a connectivity graph, while in sensor information-based all control decisions are based on processing the current sensor's data. A maze with no pre-model available is called unknown maze, while an imperfect maze is the one which has loops or closed circuits. Most of the traditional information-based unknown-maze traversal techniques are based on trial and error, which are time-consuming and may trap the robot in infinite loops or dead ends. To address the above issues, this paper proposed a gap-based approach for imperfect unknown mazes traversal named Follow the Nearest-to-final goal and Unvisited Gap (FNUG) for the first time. The algorithm is computationally efficient, and has the ability to deal with loops and dead ends through the revisit check. The main part of this approach is finding out gaps around the robot by analyzing the depth scans, building a coordinate system based topological map in the form of a tree. Then a heuristic selection of robot's unvisited-neighbor gap for navigation based on its Euclidean distance with the final target location. Compared to existing sensor information-based methods, our proposed algorithm not only takes into account the current sensor data, the shape and size of the robot, but also all the sub goals visited so far. This is the key factor of our algorithm that prevents the robot from falling into a dead end or trapping in a loop. To prove the effectiveness of this algorithm, simulations and physical experiments were performed using using a 2-wheeled differential mobile robot.