Path Planning Method Based on D~* lite Algorithm for Unmanned Surface Vehicles in Complex Environments

In recent decades, path planning for unmanned surface vehicles(USVs) in complex environments, such as harbours and coastlines, has become an important concern. The existing algorithms for real-time path planning for USVs are either too slow at replanning or unreliable in changing environments with multiple dynamic obstacles. In this study,we developed a novel path planning method based on the D* lite algorithm for real-time path planning of USVs in complex environments. The proposed method has the following advantages:(1) the computational time for replanning is reduced significantly owing to the use of an incremental algorithm and a new method for modelling dynamic obstacles;(2) a constrained artificial potential field method is employed to enhance the safety of the planned paths; and(3) the method is practical in terms of vehicle performance. The performance of the proposed method was evaluated through simulations and compared with those of existing algorithms. The simulation results confirmed the efficiency of the method for real-time path planning of USVs in complex environments.     

一种基于改进蚁群算法的载人潜水器全局路径规划

当前关于使用蚁群算法解决载人潜水器路径规划问题的研究,往往只注重路径的长度和算法收敛速度,容易忽略路径点与障碍物之间的距离和路径的平滑度等要素。载人潜水器过于靠近障碍物航行时容易产生碰撞;按照不平滑路径行驶时,频繁地转向会降低航行效率。为解决这些问题,受人工势场法启发,文中在蚁群算法的概率选择环节引入障碍物惩罚因子φ和转向惩罚因子ψ,对路径点的选择加以限制。仿真测试表明,相比于传统蚁群算法和Dijkstra算法,该算法规划的路径与障碍物之间保持安全距离且转向次数更少,因此载人潜水器按照此路径航行时,安全性和航行效率更高。     

Underwater vehicle obstacle avoidance and path planning using amulti-beam forward looking sonar

This paper describes a new framework for segmentation of sonar images, tracking of underwater objects and motion estimation. This framework is applied to the design of an obstacle avoidance and path planning system for underwater vehicles based on a multi-beam forward looking sonar sensor. The real-time data flow (acoustic images) at the input of the system is first segmented and relevant features are extracted. We also take advantage of the real-time data stream to track the obstacles in following frames to obtain their dynamic characteristics. This allows us to optimize the preprocessing phases in segmenting only the relevant part of the images. Once the static (size and shape) as well as dynamic characteristics (velocity, acceleration,…) of the obstacles have been computed, we create a representation of the vehicle's workspace based on these features. This representation uses constructive solid geometry (CSG) to create a convex set of obstacles defining the workspace. The tracking takes also into account obstacles which are no longer in the field of view of the sonar in the path planning phase. A well-proven nonlinear search (sequential quadratic programming) is then employed, where obstacles are expressed as constraints in the search space. This approach is less affected by local minima than classical methods using potential fields. The proposed system is not only capable of obstacle avoidance but also of path planning in complex environments which include fast moving obstacles. Results obtained on real sonar data are shown and discussed. Possible applications to sonar servoing and real-time motion estimation are also discussed     

多障碍环境中基于增强式学习的势场优化和机器人路径规划

该文把增强式学习方法应用于多障碍环境中机器人路径规划 ,并将增强式学习和路径规划相结合 ,通过工作空间势场的自适应优化学习 ,实现机器人的全局路径规划 ,即得到从任何初始位置开始的最优路径。与传统的人工势场方法相比 ,该方法避免了势场中局部极小点所引起的陷阱区域 ,并且所得到的路径具有最优特性。计算机仿真实验结果表明 ,这种学习方法能有效的解决多障碍环境中的机器人路径规划问题     

Smoothed A* algorithm for practical unmanned surface vehicle path planning

An effective path planning or route planning algorithm is essential for guiding unmanned surface vehicles (USVs) between way points or along a trajectory. The A* algorithm is one of the most efficient algorithms for calculating a safe route with the shortest distance cost. However, the route generated by the conventional A* algorithm is constrained by the resolution of the map and it may not be compatible with the non-holonomic constraint of the USV. In this paper an improved A* algorithm has been proposed and applied to the Springer USV. A new path smoothing process with three path smoothers has been developed to improve the performance of the generated route, reducing unnecessary ‘jags’, having no redundant waypoints and offering a more continuous route. Both simulation and experimental results show that the smoothed A* algorithm outperforms the conventional algorithm in both sparse and cluttered environments that have been uniformly rasterised. It has been demonstrated that the proposed improved A* route planning algorithm can be applied to the Springer USV providing promising results when tracking trajectories.     

Multi-Behavior Fusion Based Potential Field Method for Path Planning of Unmanned Surface Vessel

The problem of the unmanned surface vessel(USV) path planning in static and dynamic obstacle environments is addressed in this paper. Multi-behavior fusion based potential field method is proposed, which contains three behaviors: goal-seeking, boundary-memory following and dynamic-obstacle avoidance. Then, different activation conditions are designed to determine the current behavior. Meanwhile, information on the positions, velocities and the equation of motion for obstacles are detected and calculated by sensor data. Besides, memory information is introduced into the boundary following behavior to enhance cognition capability for the obstacles, and avoid local minima problem caused by the potential field method. Finally, the results of theoretical analysis and simulation show that the collision-free path can be generated for USV within different obstacle environments, and further validated the performance and effectiveness of the presented strategy.     

Evolutionary path planning for autonomous underwater vehicles in a variable ocean

This paper proposes a genetic algorithm (GA) for path planning of an autonomous underwater vehicle in an ocean environment characterized by strong currents and enhanced space-time variability. The goal is to find a safe path that takes the vehicle from its starting location to a mission-specified destination, minimizing the energy cost. The GA includes novel genetic operators that ensure the convergence to the global minimum even in cases where the structure (in space and time) of the current field implies the existence of different local minima. The performance of these operators is discussed. The proposed algorithm is suitable for situations in which the vehicle has to operate energy-exhaustive missions.     

Closed-loop randomized kinodynamic path planning for an autonomous underwater vehicle

A randomized kinodynamic path planning algorithm based on the incremental sampling-based method is proposed here as the state-of-the-art in this field applicable in an autonomous underwater vehicle. Designing a feasible path for this vehicle from an initial position and velocity to a target position and velocity in three-dimensional spaces by considering the kinematic constraints such as obstacles avoidance and dynamic constraints such as hard bounds and non-holonomic characteristic of AUV are the main motivation of this research. For this purpose, a closed-loop rapidly-exploring random tree (CL-RRT) algorithm is presented. This CL-RRT consists of three tightly coupled components: a RRT algorithm, three fuzzy proportional-derivative controllers for heading and diving control and a six degree-of-freedom nonlinear AUV model. The branches of CL-RRT are expanded in the configuration space by considering the kinodynamic constraints of AUV. The feasibility of each branch and random offspring vertex in the CL-RRT is checked against the mentioned constraints of AUV. Next, if the planned branch is feasible by the AUV, then the control signals and related vertex are recorded through the path planner to design the final path. This proposed algorithm is implemented on a single board computer (SBC) through the xPC Target and then four test-cases are designed in 3D space. The results of the processor-in-the-loop tests are compared by the conventional RRT and indicate that the proposed CL-RRT not only in a rapid manner plans an initial path, but also the planned path is feasible by the AUV.     

基于DIDSON的未知海域覆盖规划算法

针对自主水下机器人的路径规划问题,提出一种基于双频识别侧扫声呐(DIDSON)的全局路径规划算法。根据双频识别侧扫声呐的物理特性对AUV进行数学建模,根据声呐的工作频率不同,将AUV分为高频、低频两种工作模式。高频模式下成像精度高,低频模式下成像范围大。文中提出了一种D2-CPP算法,根据声呐返回的识别结果,算法会自主切换AUV的工作模式,并动态规划出对应的路径点,直到覆盖所有区域。通过与割草机算法的仿真对比,证明了算法的有效性,近海实验证明了算法的可靠性。     

The coupled oceanographic–tomographic analysis and prediction system: A practical means for utilizing high frequency tomography in the world's oceans

Details are presented of a methodology that utilizes acoustic travel time information in an ocean circulation model. Recent developments of this model-oriented tomography are discussed, representing some significant improvements over earlier formulations. More accurate means of determining the arrival times of specific ray paths are detailed, along with a means of estimating possible errors in the calculated travel times. The assimilation of the observed arrival time information into an ocean model is achieved using a Kalman gain, and more advanced expressions for calculating the Kalman gain are presented. A formulation to account for errors in the stated positions of a source and receiver is also presented. It is shown that the methodology performs fairly well in reproducing observed travel time anomalies. However, the model-predicted anomalies along a specific ray path may not always track the observed anomalies for that path when assimilating multiple ray path data. Results indicate that additional work is required to determine a means of handling observed arrival time data without having prior knowledge of the magnitude of errors in the observations. Results from simulation experiments provide estimates of: (1) potential errors when the travel times for ray paths are only sampled at discreet intervals as opposed to continuously and (2) to what degree acoustic data can be expected to “correct” model-predicted fields.     

顾及恶劣海况的船舶救援路径规划

为了保障救援船舶在恶劣海况环境下能够安全、高效地到达救援区域,本文改进人工鱼群算法开展海上救援路径规划研究.选取地形、海风和海浪等指标进行风险度量,采用GIS(geographical infor-mation system)多指标决策方法构建海洋环境威胁场,通过粒子群算法计算救援路径规划的最佳参数,并实现海上救援路径...     

Temporal-spatial oceanic variation in relation with the three typical Kuroshio paths south of Japan

Empirical orthogonal function(EOF) analysis was applied to a 50-year long time series of monthly mean positions of the Kuroshio path south of Japan from a regional reanalysis. Three leading EOF modes characterize the contributions from three typical paths of the Kuroshio meander: the typical large meander path, the offshore nonlarge meander path, and the nearshore non-large meander path, respectively. Accordingly, the spatial variation characteristics of oceanic anomaly fields can be depicted by...     

Planar trajectory planning and tracking control design for underactuated AUVs

This paper addresses the combined problem of trajectory planning and tracking control for underactuated autonomous underwater vehicles (AUVs) on the horizontal plane. Given a smooth, inertial, 2D reference trajectory, the planning algorithm uses vehicle dynamics to compute the reference orientation and body-fixed velocities. Using these, the error dynamics are obtained. These are stabilized using backstepping techniques, forcing the tracking error to an arbitrarily small neighborhood of zero. Simulation results for a constant velocity trajectory, i.e. a circle, and a time-varying velocity one, i.e. a sinusoidal path, are presented. The parametric robustness is considered and it is shown that tracking remains satisfactory.     

Real-time path planning and obstacle avoidance for RAIS: anautonomous underwater vehicle

This paper describes a navigation and guidance system (NGS) with real-time path planning and obstacle avoidance capabilities that has been developed for the autonomous underwater vehicle RAIS. The vehicle is designed to accomplish two missions: pre-deployment survey of sea bottom, and visual inspection of pipelines. In the first mission, the NGS must be able to track a predefined path while avoiding the unplanned occurrence of obstacles. In the second mission, the NGS must track a pipeline by locally reconstructing its location from visual information; also in this case, the unplanned occurrence of obstacles must be handled. Furthermore, the NGS must properly take into account the presence of ocean current and some drastic constraints due to sensor and actuator characteristics. Numerical and hardware-in-the-loop simulations have been developed to verify the effectiveness of the proposed NGS     

基于蚁群算法深海采矿机器人工作路径规划

针对深海采矿机器人路径规划问题,提出一种适合于采矿作业的改进蚁群算法。该算法利用位图法建立环境模型,依据构型空间的思想将路径规划问题简化为质点运动问题;利用改进的蚁群算法对问题进行描述,蚁群搜索中采用邻居搜索原则和中线偏移策略。最后通过仿真实验表明,该算法精度高,在海底环境中,能够完成机器人采矿作业的要求。     

A steady model of typical non-large-meander paths of the Kuroshio Current

Conditions south of Cape Shiono-misaki for the nearshore and offshore non-large-meander (NLM) paths of the Kuroshio Current are studied using a two-layer reduced gravity model. A steady and non-diffusive state is assumed, and the conservation laws of Bernoulli's function and potential vorticity along the current axis are used. Spatial changes of velocity and depth of the current are imposed as boundary conditions south of Cape Shiono-misaki. These conditions are based on the facts that are ohserved south of the cape: abrupt acceleration of the Kuroshio and the spatial change of sea levels. The current paths east of the cape are computed.This model reproduces well the actual nearshore NLM paths. It also produces offshore NLM paths west of and over the Izu Ridge, but not east of the Izu Ridge. Diffusion of vorticity may be important for the eastern part of the offshore NLM path.An increase of velocity south of the cape is necessary for producing realistic NLM paths. The velocity increase accompanies a decrease of current depth owing to Bernoulli's conservation, and the depth decrease in turn diminishes the absolute vorticity owing to the potential vorticity conservation. The velocity increase, on the other hand, strengthens the negative velocity shear and diminishes the relative vorticity. If the decreases of the relative and absolute vorticities compensate each other, the path goes excessively southward owing to the negative curvature south of the cape. Dominance of the relative vorticity change over the absolute vorticity change prevents, the path from shifting southward and causes the realistic NLM paths.The NLM paths need different amplitudes of the changes south of the cape depending on the velocity and transport of the current, but in any case, the nearshore NLM path needs larger changes than the offshore NLM path. This property and the amplitude of the changes are consistent with observations.     

一种基于有限状态机模型的局部转向避碰路径规划算法

针对多礁石、渔船等障碍物的近海复杂环境下的一些应用,提出了一种基于有限状态机(finite-state machine,FSM)模型的无人船(unmanned surface vehicle,USV)局部转向避碰路径规划算法。首先,基于速度障碍法和障碍物区域分层方法,获取无人船固定航速条件下的航向角约束解析结果。然后,基于该约束条件及障碍物探测情况设计FSM的有限状态及执行动作和状态迁移条件,其中,通过转向控制实现向目标位点或缓冲位点进行导航的状态为FSM的2个重要状态。最终通过FSM的执行实现局部转向避碰路径规划。仿真结果表明提出的多障碍物避碰算法具有可行性和实用性。该方法易于改进和扩展,且容易与当前主流的无人船控制系统结合,有利于无人船避碰系统快速工程化的实现。     

在狭窄通道环境下书库管理机器人的最优路径规划

研究移动机器人在狭窄通道环境下的定位和路径规划问题。首先,根据在书架和图书上预置的射频识别(RFID)标签,利用RFID技术提出了确定书库管理机器人位置和姿态的方法。然后,根据书库的书架间通道狭窄的特点,将书库管理机器人的行驶状态分解为匀速直线运动和原地匀速旋转运动,并给出了机器人匀速直线运动和原地匀速旋转运动的用时模型。最后,提出一种书库管理机器人从任意起始位置和姿态到达任意目标位置的最小用时路径规划算法。仿真结果表明,本文提出的路径规划算法是有效的。     

基于A星算法的无人机路径规划优化模型研究

在分析传统无人机路径规划方法应用局限的基础上,针对传统A星算法启发函数单一、拐点冗余,以及效率不够高等系列问题,以虚拟城市地理环境为研究背景,通过提出面向起讫节点方位角的A星算法加速优化、启发式搜索中动态加权重构评价函数的A星算法加速优化和顾及Floyd算法插点策略的A星算法路径优化等层次递进的算法优化策略,解决了对A星算法搜索方向的量化约束、搜索权重数值的优化重构及冗余拐点的插点删除等技术问题,实现了改进后的A星算法运行效率的显著提高及最短路径判定准确性的明显提升。     

Water and flow variations in Sagami Bay under the influence of the Kuroshio path

Variations of water and flow in Sagami Bay in relation to the Kuroshio path variations are examined by using 100m-depth temperature and salinity data from 25 stations as well as sea level data from five stations (Minami-Izu, ItÔ, Ôshima, Aburatsubo, Mera). In regard to temperature, anomalies from the mean seasonal variations are used. Results show that water properties are clearly different between the three typical paths of the Kuroshio. The difference is more remarkable in temperature than in salinity; temperature is higher during the typical large-eander (LM) path, and lower during the offshore non-large-meander (NLM) path, compared with the nearshore NLM path. Temperature anomaly and salinity distributions, as well as the Ôshima minus Minami-Izu and Ôshima minus Mera sea-level differences strongly suggest that the flows during the typical LM path are distributed as hitherto described in past studies, that is, water in the mouth region of the bay flows clockwise around Ôshima from the west channel to the east channel, and a counterclockwise eddy exists in the interior. On the other hand, flows during the nearshore and offshore NLM paths seem to be quite different from those during the typical LM path; velocities are very weak, and the directions of circulation is frequently reversed. This tendency also can be seen during parts of LM period in which the Kuroshio takes a non-typical LM path.Water properties in Sagami Bay are most characteristic during transitions between nearshore and offshore NLM paths. During transitions from nearshore to offshore NLM paths, temperatures are extremely high as a whole in the bay, while during reverse transitions, both temperatures and salinities are very low in the entire region.