Neural computation for collision-free path planning

Automatic path planning plays an essential role in planning of assembly or disassembly of products, motions of robot manipulators handling part, and material transfer by mobile robots in an intelligent and flexible manufacturing environment. The conventional methodologies based on geometric reasoning suffer not only from the algorithmic difficulty but also from the excessive time complexity in dealing with 3-D path planning. This paper presents a massively parallel, connectionist algorithm for collision-free path planning. The path planning algorithm is based on representing a path as a series ofvia points or beads connected by elastic strings which are subject to displacement due to a potential field or a collision penalty function generated by polyhedral obstacles. Mathematically, this is equivalent to optimizing a cost function, defined in terms of the total path length and the collision penalty function, by moving thevia points simultaneously but individually in the direction that minimizes the cost function. Massive parallelism comes mainly from: (1) the connectionist model representation of obstacles and (2) the parallel computation of individualvia-point motions with only local information. The algorithm has power to deal effectively with path planning of three-dimensional objects with translational and rotational motions. Finally, the algorithm incorporates simulated annealing to solve a local minimum problem. Simulation results are shown.     

Real-Time Collision-Free Path Planning for Robots in Configuration Space

Collision-free path planning for an industrial robot in configuration space requires mapping obstacles from robot‘s workspace into its configuration space.In this paper,an approach to real-time collision-free path planning for robots in configuration space is presented.Obstacle mapping is carried out by fundamental obstacles defined in the workspace and their images in the configuration space.In order to avoid dealing with unimportant parts of the configuration space that do not affect searching a collision-free path between starting and goal configurations,we construct a free subspace by slice configuration obstacles.In this free subspace,the collision-free path is determined by the A^* algorithm.Finally,graphical simulations show the effectiveness of the proposed approach.     

Case-based path planning for autonomous underwater vehicles

Case-based reasoning is reasoning based on specific instances of past experience. A new solution is generated by retrieving and adapting an old one which approximately matches the current situation. In this paper, we outline a case-based reasoning scheme for path planning in autonomous underwater vehicle (AUV) missions. An annotated map database is employed to model the navigational environment. Routes which are used in earlier missions are represented as objects in the map. When a new route is to be planned, the path planner retrieves a matching route from the database and modifies it to suit to the current situation. Whenever a matching route is not available, a new route is synthesized based on past cases that describe similar navigational environments. Case-based approach is thus used not only to adapt old routes but also to synthesize new ones. Since the proposed scheme is centered around reuse of old routes, it would be fast especially when long routes need to be generated. Moreover, better reliability of paths can be expected as they are adapted from earlier missions. The scheme is novel and appropriate for AUV mission scenarios. In this paper, we describe the representation of navigation environment including past routes and objects in the navigational space. Further, we discuss the retrieval and repair strategies and the scheme for synthesizing new routes. Sample results of both synthesis and reuse of routes and system performance analysis are also presented. One major advantage of this system is the facility to enrich the map database with new routes as they are generated.This work was supported in part by National Science Foundation Grant No. BCS-9017990.     

A path planning algorithm for industrial robots

Instead of using the tedious process of robot teaching, an off-line path planning algorithm has been developed for industrial robots to improve their accuracy and efficiency. Collision avoidance is the primary concept to achieve such goal. By use of the distance maps, the inspection of obstacle collision is completed and transformed to the configuration space in terms of the robot joint angles. On this configuration map, the relation between the obstacles and the robot arms is obvious. By checking the interference conditions, the collision points are indicated with marks and collected into the database. The path planning is obtained based on the assigned marked number of the passable region via wave expansion method. Depth-first search method is another approach to obtain minimum sequences to pass through. The proposed algorithm is experimented on a 6-DOF industrial robot. From the simulation results, not only the algorithm can achieve the goal of collision avoidance, but also save the manipulation steps.     

月球表面巡视探测自主局部避障规划

路径规划是月球表面巡视探测自主导航的重要功能,是提高地外天体表面探测效率和安全性的关键.国外已实现的地外天体表面自主路径规划方法以局部避障为主要目标,不考虑全局目标可达性和完备性,本文针对该问题,提出一种基于地形通过性定量评价和目标可达的综合自主局部避障规划方法,通过对稠密地形数据进行可通过性能的综合评价,并考虑与目标的方位和距离,规划出能够到达目标的避障安全路径.该方法已经成功应用于我国"玉兔号"和"玉兔二号"月球车的自主导航中.     

Algorithms for path planning, navigation and guidance of an AGV

Algorithms for path navigation and generation of guidance setpoints for an AGV are developed. Navigation is based on a simple flat world model of connected nodes using a suboptimal path solution for execution speed. The guidance algorithms use vision data from a stereo pair of linear image array cameras, which described an obstacle location and height where intersected by the vision system plane of view. The development of a map of the area on the AGV path allows the detection of obstacles, which may be passed subject to the aisle markings. The complete vision-guidance system can be implemented using inexpensive commercially available 16 bit microprocessors.     

Dyna-Q-based vector direction for path planning problem of autonomous mobile robots in unknown environments

Reinforcement learning (RL) is a popular method for solving the path planning problem of autonomous mobile robots in unknown environments. However, the primary difficulty faced by learning robots using the RL method is that they learn too slowly in obstacle-dense environments. To more efficiently solve the path planning problem of autonomous mobile robots in such environments, this paper presents a novel approach in which the robot’s learning process is divided into two phases. The first one is to accelerate the learning process for obtaining an optimal policy by developing the well-known Dyna-Q algorithm that trains the robot in learning actions for avoiding obstacles when following the vector direction. In this phase, the robot’s position is represented as a uniform grid. At each time step, the robot performs an action to move to one of its eight adjacent cells, so the path obtained from the optimal policy may be longer than the true shortest path. The second one is to train the robot in learning a collision-free smooth path for decreasing the number of the heading changes of the robot. The simulation results show that the proposed approach is efficient for the path planning problem of autonomous mobile robots in unknown environments with dense obstacles.     

基于强化学习的自动驾驶汽车路径规划方法研究综述

路径规划作为自动驾驶的关键技术,具有广阔的应用前景和科研价值。探索解决自动驾驶车辆路径规划问题的方法,着重关注基于强化学习的路径规划方法。在阐述基于常规方法和强化学习方法的路径规划技术的基础上,重点总结了基于强化学习和深度强化学习来解决自动驾驶车辆路径规划问题的算法,并将算法按照基于值和基于策略的方式进行分类,分析各类算法的特点、优缺点及改进措施。最后对基于强化学习的路径规划技术的未来发展方向进行了展望。     

自治水下机器人的自主启发式生物启发神经网络路径规划算法

针对复杂海流环境下自治水下机器人(autonomous underwater vehicle, AUV)的路径规划问题,本文在栅格地图的基础上给出了一种基于离散的生物启发神经网络(Glasius bio-inspired neural networks, GBNN)模型的新型自主启发式路径规划和安全避障算法,并考虑海流对路径规划的影响.首先建立GBNN模型,利用此模型表示AUV的工作环境,神经网络中的每一个神经元与栅格地图中的位置单元一一对应;其次,根据神经网络中神经元的活性输出值分布情况并结合方向信度算法实现自主规划AUV的运动路径;最后根据矢量合成算法确定AUV实际的航行方向.障碍物环境和海流环境下仿真实验结果表明了生物启发模型在AUV水下环境中路径规划的有效性.     

Three-dimensional optimal path planning for waypoint guidance of an autonomous underwater vehicle

In this paper, optimal three-dimensional paths are generated offline for waypoint guidance of a miniature Autonomous Underwater Vehicle (AUV). Having the starting point, the destination point, and the position and dimension of the obstacles, the AUV is intended to systematically plan an optimal path toward the target. The path is defined as a set of waypoints to be passed by the vehicle. Four criteria are considered for evaluation of an optimal path; they are “total length of path”, “margin of safety”, “smoothness of the planar motion” and “gradient of diving”. A set of Pareto-optimal solutions is found where each solution represents an optimal feasible path that cannot be outrun by any other path considering all four criteria. Then, a proposed three-dimensional guidance system is used for guidance of the AUV through selected optimal paths. This system is inspired from the Line-of-Sight (LOS) guidance strategy; the idea is to select the desired depth, presumed proportional to the horizontal distance of the AUV and the target. To develop this guidance strategy, the dynamic modeling of this novel miniature AUV is also derived. The simulation results show that this guidance system efficiently guides the AUV through the optimal paths.     

Adaptive path planning and tracking system based on model predictive control for autonomous vehicle local obstacle avoidance

Path planning and tracking control are the key technologies of autonomous vehicle. The planned path and tracking results affect driving stability and safety directly. In this paper, an improved local path planning method based on model predictive control is proposed to match the variation of vehicle speed and road adhesion coefficient. A two-layer model predictive control (MPC) path planning and tracking system is further designed to validate the method and the simulation results show that the proposed solution solves the problem of excessive avoidance and reduces the lateral deviation with the reference path.     

基于深度时空Q网络的定向导航自动驾驶运动规划

针对目前基于机器学习的自动驾驶运动规划需要大量样本、没有关联时间信息,以及没有利用全局导航信息等问题,提出一种基于深度时空Q网络的定向导航自动驾驶运动规划算法。首先,为提取自动驾驶的空间图像特征与前后帧的时间信息,基于原始深度Q网络,结合长短期记忆网络,提出一种新的深度时空Q网络;然后,为充分利用自动驾驶的全局导航信息,在提取环境信息的图像中加入指向信号来实现定向导航的目的;最后,基于提出的深度时空Q网络,设计面向自动驾驶运动规划模型的学习策略,实现端到端的运动规划,从输入的序列图像中预测车辆方向盘转角和油门刹车数据。在Carla驾驶模拟器中进行训练和测试的实验结果表明,在四条测试道路中该算法平均偏差均小于0.7 m,且稳定性能优于四种对比算法。该算法具有较好的学习性、稳定性和实时性,能够实现在全局导航路线下的自动驾驶运动规划。     

不确定海流环境下水下机器人最优时间路径规划

为解决海流预测不精确条件下,现有基于确定性海流路径规划算法鲁棒性差和规划的路径有可能为不可行路径的问题,本文提出一种基于区间优化的水下机器人(AUV)最优时间路径规划算法.该算法采用双层架构,外层用蚁群系统算法(ACS)寻找由起点至终点的候选路径;内层以区间海流为环境模型,计算候选路径航行时间上下限,并分别通过区间序关系和基于可靠性的区间可能度模型将航行时间区间转换为确定性评价函数,并将评价函数值作为候选路径适应度值返回到外层算法.仿真结果表明,相对于确定海流场路径规划方案,提出的方案增强了路径规划器的鲁棒性并解决了结果路径不可行问题.     

A simple algorithm for intelligent manipulator collision-free motion

The collision-free planning of motion is a fundamental problem for artificial intelligence applications in robotics. The ability to compute a continuous safe path for a robot in a given environment will make possible the development of task-level robot planning systems so that the implementation details and the particular robot motion sequence will be ignored by the programmer.A new approach to planning collision-free motions for general real-life six degrees of freedom (d.o.f.) manipulators is presented. It is based on a simple object model previously developed. The complexity of the general collision detection problem is reduced, and realistic collision-free paths are efficiently found onCS planes. A heuristic evaluation function with a real physical sense is introduced, and computational cost is reduced to the strictly necessary by selecting the most adequate level of representation. A general algorithm is defined for 6 d.o.f. robots that yields good results for actual robot models with complex design structures with the aid of various heuristic techniques. The problem of adaptive motion is also considered.     

面向自动驾驶的动态路径规划避障算法

针对自动驾驶中避障的动态路径规划问题,提出一种在已知车辆的初始位置、速度、方向和障碍物位置情况下,实时避开障碍物的动态规划算法。首先,利用三次样条曲线的二阶连续性,结合已知的车道信息产生道路基准线;其次,以车辆的位置方向和道路的曲率构建s-q坐标系,并在s-q坐标系内产生从车辆当前位置到目的位置的一簇平滑曲线,作为候选路径;最后,综合考虑车辆行驶的安全性、平滑性和连贯性准则,设计一种新的代价函数,并且通过使代价函数最小化的方法从候选路径中选择最佳路径。在实验过程中,通过设计多种不同的模拟道路来检验算法的性能。实验结果表明,该方法在多种地形的单车道和多车道道路上都能够规划出安全、平滑的路径,有效避开障碍物,并且具有较好的实时性。     

Real-time path planning with limited information for autonomous unmanned air vehicles

We propose real-time path planning schemes employing limited information for fully autonomous unmanned air vehicles (UAVs) in a hostile environment. Two main algorithms are proposed under different assumptions on the information used and the threats involved. They consist of several simple (computationally tractable) deterministic rules for real-time applications. The first algorithm uses extremely limited information (only the probabilistic risk in the surrounding area with respect to the UAV's current position) and memory, and the second utilizes more knowledge (the location and strength of threats within the UAV's sensory range) and memory. Both algorithms provably converge to a given target point and produce a series of safe waypoints whose risk is almost less than a given threshold value. In particular, we characterize a class of dynamic threats (so-called, static-dependent threats) so that the second algorithm can efficiently handle such dynamic threats while guaranteeing its convergence to a given target. Challenging scenarios are used to test the proposed algorithms.     

Guided Autowave Pulse Coupled Neural Network (GAPCNN) based real time path planning and an obstacle avoidance scheme for mobile robots

Real time path planning for mobile robots requires fast convergence to optimal paths. Most rapid collision free path planning algorithms do not guarantee the optimality of the path. In this paper we present a Guided Autowave Pulse Coupled Neural Network (GAPCNN) approach for mobile robot path planning. The proposed model is a novel approach that improves upon the recently presented Modified PCNN (MPCNN) by introducing directional autowave control and accelerated firing of neurons based on a dynamic thresholding technique. Simulation studies and experimental results in both static as well as dynamic environments confirm GAPCNN to be a robust and time efficient path planning scheme for finding optimal paths.     

Neural robot path planning: The maze problem

The importance of path planning is very significant in the field of robotics. This paper presents the application of multilayer perceptrons to the robot path planning problem, and in particular to the task of maze navigation. Previous published results implied that the training of feedforward multilayered networks failed, because of the non- smoothness of data. Here the path planning problem is reconsidered, and it is shown that multilayer perceptrons are able to learn the task successfully.