Czech Institute of Informatics, Robotics, and Cybernetics, Czech Technical University in Prague, 160 00 Prague,Czech Republic.
Sensors (Basel). 2019 Mar 21;19(6):1400. doi: 10.3390/s19061400.
This paper deals with the problem of autonomous navigation of a mobile robot in an unknown2D environment to fully explore the environment as efficiently as possible. We assume a terrestrial mobilerobot equipped with a ranging sensor with a limited range and 360º field of view. The key part of theexploration process is formulated as the d-Watchman Route Problem which consists of two coupledtasks-candidate goals generation and finding an optimal path through a subset of goals-which aresolved in each exploration step. The latter has been defined as a constrained variant of the GeneralizedTraveling Salesman Problem and solved using an evolutionary algorithm. An evolutionary algorithmthat uses an indirect representation and the nearest neighbor based constructive procedure was proposedto solve this problem. Individuals evolved in this evolutionary algorithm do not directly code thesolutions to the problem. Instead, they represent sequences of instructions to construct a feasible solution.The problems with efficiently generating feasible solutions typically arising when applying traditionalevolutionary algorithms to constrained optimization problems are eliminated this way. The proposedexploration framework was evaluated in a simulated environment on three maps and the time needed toexplore the whole environment was compared to state-of-the-art exploration methods. Experimentalresults show that our method outperforms the compared ones in environments with a low density ofobstacles by up to 12.5%, while it is slightly worse in office-like environments by 4.5% at maximum.The framework has also been deployed on a real robot to demonstrate the applicability of the proposedsolution with real hardware.
本文研究了在未知 2D 环境中自主导航的移动机器人问题，旨在尽可能高效地探索环境。我们假设一个配备有限范围和 360°视野测距传感器的地面移动机器人。探索过程的关键部分被表述为 d-Watchman 路径问题，它由两个耦合任务组成——候选目标生成和通过目标子集找到最优路径——在每个探索步骤中解决。后者被定义为广义旅行商问题的约束变体，并使用进化算法求解。提出了一种使用间接表示和基于最近邻的构造过程的进化算法来解决这个问题。在这种进化算法中，个体不直接对问题的解进行编码。相反，它们代表构造可行解的指令序列。通过这种方式，可以消除在应用传统进化算法解决约束优化问题时通常出现的高效生成可行解的问题。所提出的探索框架在三个地图的模拟环境中进行了评估，并比较了探索整个环境所需的时间与最先进的探索方法。实验结果表明，在障碍物密度较低的环境中，我们的方法比比较方法的性能高出 12.5%，而在类似于办公室的环境中，我们的方法的性能则略差 4.5%。该框架还已部署在真实机器人上，以展示所提出的解决方案在真实硬件中的适用性。
