动态环境下改进人工势场法的仓储机器人自主导航系统研究

为了解决仓储机器人在全动态环境中的自主导航问题,在分析自主导航技术基础上建立了机器人和动态障碍物的数学模型,搭建了以二维激光雷达为主的环境感知平台,提出了一种改进的人工势场法。在传统人工势场法中同时引入相对速度和相对加速度因素得到改进的人工势场模型,实现机器人在全动态环境中的自主移动。设计了无障碍物和多动态障碍物两种移动环境。经仿真验证,应用改进的人工势场法进行路径规划能高效地避开动态障碍物、跟踪动态目标,且运动路径光滑。     

A navigation mesh for dynamic environments

Games and simulations frequently model scenarios where obstacles move, appear, and disappear in an environment. A city environment changes as new buildings and roads are constructed, and routes can become partially blocked by small obstacles many times in a typical day. This paper studies the effect of using local updates to repair only the affected regions of a navigation mesh in response to a change in the environment. The techniques are inspired by incremental methods for Voronoi diagrams. The main novelty of this paper is that we show how to maintain a 2D or 2.5D navigation mesh in an environment that contains dynamic polygonal obstacles. Experiments show that local updates are fast enough to permit real‐time updates of the navigation mesh. Copyright © 2012 John Wiley & Sons, Ltd.     

Space‐time planning in changing environments : using dynamic objects for accessibility

Navigation is a critical task for agents populating virtual worlds. In the last years, numerous solutions have been proposed to solve the path planning problem in order to enhance the autonomy of virtual agents. Those solutions mainly focused on static environments, eventually populated with dynamic obstacles. However, dynamic objects are usually more than just obstacles as they can be used by an agent to reach new locations. In this paper, we propose an online path planning algorithm in dynamically changing environments with unknown evolution such as physically based‐environments. Our method represents objects in terms of obstacles but also in terms of navigable surfaces. This representation allows our algorithm to find temporal paths through disconnected and moving platforms. We will also show that the proposed method also enables several kinds of adaptations such as avoiding moving obstacles or adapting the agent postures to environmental constraints. Copyright © 2012 John Wiley & Sons, Ltd.     

机器人导航系统中的路径规划算法

导航系统是反映移动机器人自主特性与智能行为的关键问题之一,它所能完成的功能包括:环境的感知与识别、路径规划、路径跟踪、障碍回避等。路径规划是移动机器人导航技术中的重要组成部分,它是机器人执行各种任务的基础,而如何在动态时变环境中有效的实施路径规划是亟待解决的问题。本文综述了该领域研究的主要内容及其发展动态,在对一些较有代表性的研究思想及其相关算法分析的基础上,指出了存在的不足和有待进一步研究的问题,并提出了一些解决思路。     

导航系统中多目标路径平滑化规划的研究

路径规划是车辆、机器人出行、无人机航路推荐和计算机游戏等许多应用中的关键任务。现有的大多路径规划常简化为单目标优化问题进行求解。但在现实生活中,还需要同时考虑多种规划目标,且用于规划路径的目标之间还存在着彼此不能变换的问题。在熟知的路径规划算法（D*Lite）上提出了一种新的多目标路径平滑化规划算法-平滑多目标D*Lite算法。通过构造一条初始多目标平滑路径,当检测到环境变化时采用增量搜索思想,仅更新受影响结点并从当前结点重新进行规划得到一条新的多目标平滑路径。仿真结果表明,该算法不但能有效躲避突发障碍物,规划路径拐点较少,还能提高搜索效率,可有效应用于具有不同非交互规划目标的导航系统。     

动态环境下基于人工势场引导的RRT路径规划算法

现有的大多数动态RRT路径规划算法不能使规划的路径远离障碍物,这有可能导致机器人没有足够的避障时间。针对此问题,提出了一种利用人工势场引导快速扩展随机树向目标区域生长并远离障碍物的改进RRT算法APFG-RRT(artificial potential field guided RRT)。为了进一步加快算法的收敛速度、加速算法跳出局部极小值,引入了一种按自适应概率选择目标点作为采样点的策略;针对动态环境采用全局规划结合局部重新规划的方法以提高算法的实时性。仿真实验表明,相比于初始RRT和Goal-bias RRT,APFG-RRT的计算效率更高,内存需求更小,并且搜索到的路径能够有效地远离障碍物,提高了动态路径规划的成功率。     

Deliberative On-Line Local Path Planning for Autonomous Mobile Robots

This paper describes a method for local path planning for mobile robots that combines reactive obstacle avoidance with on-line local path planning. Our approach is different to other model-based navigation approaches since it integrates both global and local planning processes in the same architecture while other methods only combine global path planning with a reactive method to avoid non-modelled obstacles. Our local planning is only triggered when an unexpected obstacle is found and reactive navigation is not able to regain the initial path. A new trajectory is then calculated on-line using only proximity sensor information. This trajectory can be improved during the available time using an anytime algorithm. The proposed method complements the reactive behaviour and allows the robot to navigate safely in a partially known environment during a long time period without human intervention.     

Effective virtual reality based building navigation using dynamic loading and path optimization

Although computer capabilities have been improved significantly, a large-scale virtual reality (VR) system demands much more in terms of memory and computation than the current computer systems can offer. This paper discusses two important issues related to VR performance and applications in building navigation. These are dynamic loading of models based on cell segmentation for the optimal VR operation, and the route optimization based on path planning for easy navigation. The VR model of engineering and information technology complex (EITC) building at the University of Manitoba is built as an example to show the feasibility of the proposed methods. The reality, enhanced by three-dimensional (3D) real-time interactivity and visualization, leads navigators into a state of the virtual building immersion.     

Overview obstacle maps for obstacle‐aware navigation of autonomous drones

Achieving the autonomous deployment of aerial robots in unknown outdoor environments using only onboard computation is a challenging task. In this study, we have developed a solution to demonstrate the feasibility of autonomously deploying drones in unknown outdoor environments, with the main capability of providing an obstacle map of the area of interest in a short period of time. We focus on use cases where no obstacle maps are available beforehand, for instance, in search and rescue scenarios, and on increasing the autonomy of drones in such situations. Our vision‐based mapping approach consists of two separate steps. First, the drone performs an overview flight at a safe altitude acquiring overlapping nadir images, while creating a high‐quality sparse map of the environment by using a state‐of‐the‐art photogrammetry method. Second, this map is georeferenced, densified by fitting a mesh model and converted into an Octomap obstacle map, which can be continuously updated while performing a task of interest near the ground or in the vicinity of objects. The generation of the overview obstacle map is performed in almost real time on the onboard computer of the drone, a map of size is created in , therefore, with enough time remaining for the drone to execute other tasks inside the area of interest during the same flight. We evaluate quantitatively the accuracy of the acquired map and the characteristics of the planned trajectories. We further demonstrate experimentally the safe navigation of the drone in an area mapped with our proposed approach.     

Real‐time density‐based crowd simulation

Virtual characters in games and simulations often need to plan visually convincing paths through a crowded environment. This paper describes how crowd density information can be used to guide a large number of characters through a crowded environment. Crowd density information helps characters avoid congested routes that could lead to traffic jams. It also encourages characters to use a wide variety of routes to reach their destination. Our technique measures the desirability of a route by combining distance information with crowd density information. We start by building a navigation mesh for the walkable regions in a polygonal two‐dimensional (2‐D) or multilayered three‐dimensional (3‐D) environment. The skeleton of this navigation mesh is the medial axis. Each walkable region in the navigation mesh maintains an up‐to‐date density value. This density value is equal to the area occupied by all the characters inside a given region divided by the total area of this region. These density values are mapped onto the medial axis to form a weighted graph. An A^* search on this graph yields a backbone path for each character, and forces are used to guide the characters through the weighted environment. The characters periodically replan their routes as the density values are updated. Our experiments show that we can compute congestion‐avoiding paths for tens of thousands of characters in real‐time. Copyright © 2012 John Wiley & Sons, Ltd.     

Perception‐aware autonomous mast motion planning for planetary exploration rovers

Highly accurate real‐time localization is of fundamental importance for the safety and efficiency of planetary rovers exploring the surface of Mars. Mars rover operations rely on vision‐based systems to avoid hazards as well as plan safe routes. However, vision‐based systems operate on the assumption that sufficient visual texture is visible in the scene. This poses a challenge for vision‐based navigation on Mars where regions lacking visual texture are prevalent. To overcome this, we make use of the ability of the rover to actively steer the visual sensor to improve fault tolerance and maximize the perception performance. This paper answers the question of where and when to look by presenting a method for predicting the sensor trajectory that maximizes the localization performance of the rover. This is accomplished by an online assessment of possible trajectories using synthetic, future camera views created from previous observations of the scene. The proposed trajectories are quantified and chosen based on the expected localization performance. In this study, we validate the proposed method in field experiments at the Jet Propulsion Laboratory (JPL) Mars Yard. Furthermore, multiple performance metrics are identified and evaluated for reducing the overall runtime of the algorithm. We show how actively steering the perception system increases the localization accuracy compared with traditional fixed‐sensor configurations.     

A hybrid approach for autonomous navigation of mobile robots in partially-known environments

We propose a hybrid approach specifically adapted to deal with the autonomous-navigation problem of a mobile robot which is subjected to perform an emergency task in a partially-known environment. Such a navigation problem requires a method that is able to yield a fast execution time, under constraints on the capacity of the robot and on known/unknown obstacles, and that is sufficiently flexible to deal with errors in the known parts of the environment (unexpected obstacles). Our proposal includes an off-line task-independent preprocessing phase, which is applied just once for a given robot in a given environment. Its purpose is to build, within the known zones, a roadmap of near-time-optimal reference trajectories. The actual execution of the task is an online process that combines reactive navigation with trajectory tracking and that includes smooth transitions between these two modes of navigation. Controllers used are fuzzy-inference systems. Both simulation and experimental results are presented to test the performance of the proposed hybrid approach. Obtained results demonstrate the ability of our proposal to handle unexpected obstacles and to accomplish navigation tasks in relatively complex environments. The results also show that, thanks to its time-optimal-trajectory planning, our proposal is well adapted to emergency tasks as it is able to achieve shorter execution times, compared to other waypoint-navigation methods that rely on optimal-path planning.     

Robot navigation in a known environment with unknown moving obstacles

We propose a new type of artificial potential field, that we call hybrid potential field, to navigate a robot in situations in which the environment is known except for unknown and possibly moving obstacles. We show how to compute hybrid potential fields in real time and use them to control the motions of a real robot. Our method is tested on both a real robot and a simulated one. We present a feature matching approach for position error correction that we have validated experimentally with our mobile robot. We show extensive simulation results with up to 50 randomly moving obstacles.     

动态未知环境下一种Hopfield神经网络路径规划方法

针对动态未知环境下移动机器人路径规划问题,采用一种有效的局部连接Hopfiled神经网络(Hopfield Neural Networks,HNN)来表示机器人的工作空间.机器人在HNN所形成的动态数值势场上进行爬山搜索法来形成避碰路径,并且不存在非期望的局部吸引点.HNN权值设计中考虑了路径安全性因素,通过在障碍物附件形成局部虚拟排斥力来形成安全路径.HNN的连接权是非对称的,并且考虑了信号传播时延.分析了HNN的稳定性,所给稳定性条件和时延无关.HNN模型中突出了最大传播激励,从而使得HNN具有更广的稳定性范围并能表示具有更多节点的机器人工作空间.为对该HNN有效仿真求解,结合约束距离变换和HNN的时延性,给出了单处理器上高效的串行模拟方案,规划路径的时间复杂度为O(N)(N是HNN中神经元的数目),使得路径重规划能快速在线进行.仿真和实验表明该方法的有效性.     

动态环境下改进蚁群算法的多Agent路径规划

针对动态环境下的多Agent路径规划问题,提出了一种改进的蚁群算法与烟花算法相结合的动态路径规划方法。通过自适应信息素强度值及信息素缩减因子来加快算法的迭代速度,并利用烟花算法来解决路径规划过程中的死锁问题,避免陷入局部最优。在多Agent动态避碰过程中,根据动态障碍物与多Agent之间的运行轨迹是否相交制定相应的避碰策略,并利用路径转变函数解决多Agent的正面碰撞问题。仿真实验表明,该方法优于经典蚁群算法,能够有效解决多Agent路径规划中的碰撞问题,从而快速找到最优无碰路径。     

无线传感器网络中的分布式动态路径规划算法

利用无线传感器网络(WSN)根据环境变化为移动主体规划优化路径在实际应用中具有重要意义.针对现有梯度势场算法在动态调整方面的不足,综合考虑路径长度、安全性和通信代价,结合环境因素构造梯度势场函数,提出了一种分布式动态路径规划算法,使网络在环境变化时依据局部信息动态调整梯度势场,为每个节点提供优化路径.仿真结果显示了本文算法可使WSN在环境变化情况下,能够规划出较短路径,有效降低通信代价并灵活处理路径安全性.     

虚拟场景自动漫游的路径规划算法

采用机器人学中的运动规划算法得到大致路径,并对路径进行数次优化得到最终路径．用户无需直接控制位置与视角,仅需给出目标点,系统就会自动地完成整个漫游;漫游过程中摄像机不会与物体发生碰撞,并且给出的画面符合一些基本的美学原则．该算法基于场景的层次分解,并采用了高效的路径平滑与视角规划方法,使得整个规划过程需要的时间非常少,提高了算法的实用性．     

Reinforcement based mobile robot navigation in dynamic environment

In this paper, a new approach is developed for solving the problem of mobile robot path planning in an unknown dynamic environment based on Q-learning. Q-learning algorithms have been used widely for solving real world problems, especially in robotics since it has been proved to give reliable and efficient solutions due to its simple and well developed theory. However, most of the researchers who tried to use Q-learning for solving the mobile robot navigation problem dealt with static environments; they avoided using it for dynamic environments because it is a more complex problem that has infinite number of states. This great number of states makes the training for the intelligent agent very difficult. In this paper, the Q-learning algorithm was applied for solving the mobile robot navigation in dynamic environment problem by limiting the number of states based on a new definition for the states space. This has the effect of reducing the size of the Q-table and hence, increasing the speed of the navigation algorithm. The conducted experimental simulation scenarios indicate the strength of the new proposed approach for mobile robot navigation in dynamic environment. The results show that the new approach has a high Hit rate and that the robot succeeded to reach its target in a collision free path in most cases which is the most desirable feature in any navigation algorithm.