Samaniego Ricardo, Lopez Joaquin, Vazquez Fernando
Imatia Innovation, 36310 Vigo, Spain.
Department of Systems Engineering and Automation, School of Industrial Engineering, University of Vigo, 36310 Vigo, Spain.
Sensors (Basel). 2017 Aug 15;17(8):1876. doi: 10.3390/s17081876.
This paper presents an algorithm for finding a solution to the problem of planning a feasible path for a slender autonomous mobile robot in a large and cluttered environment. The presented approach is based on performing a graph search on a kinodynamic-feasible lattice state space of high resolution; however, the technique is applicable to many search algorithms. With the purpose of allowing the algorithm to consider paths that take the robot through narrow passes and close to obstacles, high resolutions are used for the lattice space and the control set. This introduces new challenges because one of the most computationally expensive parts of path search based planning algorithms is calculating the cost of each one of the actions or steps that could potentially be part of the trajectory. The reason for this is that the evaluation of each one of these actions involves convolving the robot's footprint with a portion of a local map to evaluate the possibility of a collision, an operation that grows exponentially as the resolution is increased. The novel approach presented here reduces the need for these convolutions by using a set of offline precomputed maps that are updated, by means of a partial convolution, as new information arrives from sensors or other sources. Not only does this improve run-time performance, but it also provides support for dynamic search in changing environments. A set of alternative fast convolution methods are also proposed, depending on whether the environment is cluttered with obstacles or not. Finally, we provide both theoretical and experimental results from different experiments and applications.
本文提出了一种算法，用于解决在大型复杂环境中为细长自主移动机器人规划可行路径的问题。所提出的方法基于在高分辨率的运动动力学可行格点状态空间上进行图搜索；然而，该技术适用于许多搜索算法。为了使算法能够考虑让机器人通过狭窄通道并靠近障碍物的路径，格点空间和控制集都采用了高分辨率。这带来了新的挑战，因为基于路径搜索的规划算法中计算量最大的部分之一是计算每个可能成为轨迹一部分的动作或步骤的成本。原因在于，对这些动作中的每一个进行评估都涉及将机器人的足迹与局部地图的一部分进行卷积，以评估碰撞的可能性，随着分辨率的提高，此操作的计算量呈指数增长。本文提出的新颖方法通过使用一组离线预计算地图来减少这些卷积的需求，这些地图会随着新的传感器信息或其他来源的信息到来，通过部分卷积进行更新。这不仅提高了运行时性能，还为在变化环境中的动态搜索提供了支持。根据环境是否布满障碍物，还提出了一组替代的快速卷积方法。最后，我们给出了来自不同实验和应用的理论及实验结果。
