Cooperative and Geometric Learning Algorithm (CGLA) for path planning of UAVs with limited information

In this paper, we propose a new learning algorithm, named as the Cooperative and Geometric Learning Algorithm (CGLA), to solve problems of maneuverability, collision avoidance and information sharing in path planning for Unmanned Aerial Vehicles (UAVs). The contributions of CGLA are three folds: (1) CGLA is designed for path planning based on cooperation of multiple UAVs. Technically, CGLA exploits a new defined individual cost matrix, which leads to an efficient path planning algorithm for multiple UAVs. (2) The convergence of the proposed algorithm for calculating the cost matrix is proven theoretically, and the optimal path in terms of path length and risk measure from a starting point to a target point can be calculated in polynomial time. (3) In CGLA, the proposed individual weight matrix can be efficiently calculated and adaptively updated based on the geometric distance and risk information shared among UAVs. Finally, risk evaluation is introduced first time in this paper for UAV navigation and extensive computer simulation results validate the effectiveness and feasibility of CGLA for safe navigation of multiple UAVs.     

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

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

Mission design for a group of autonomous guided vehicles

In this paper, a generic approach for the integration of vehicle routing and scheduling and motion planning for a group of autonomous guided vehicles (AGVs) is proposed. The AGVs are requested to serve all the work stations in a two-dimensional environment while taking into account kinematics constraints and the environment’s geometry during their motion. The problem objective is the simultaneous determination of time-optimum and collision-free paths for all AGVs. The proposed method is investigated and discussed through a number of simulated experiments using a variety of environments and different initial conditions.     

Coevolving and cooperating path planner for multiple unmanned air vehicles

In this paper, the coordinated path planning problem for multiple unmanned air vehicles is studied with the proposal of a novel coevolving and cooperating path planner. In the new planner, potential paths of each vehicle form their own sub-population, and evolve only in their own sub-population, while the interaction among all sub-problems is reflected by the definition of fitness function. Meanwhile, the individual candidates are evaluated with respect to the workspace so that the computation of the configuration space is avoided. By using a problem-specific representation of candidate solutions and genetic operators, our algorithm can take into account different kinds of mission constraints and generate solutions in real time.     

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.     

未知复杂环境中的无人机平滑飞行路径规划

针对无人机实时路径规划问题,提出了一种基于双层决策的平滑路径规划方法,以弥补现有方法在复杂飞行环境中对路径平滑性优化的不足,增强路径的易跟踪性.本文首先给出路径平滑性度量,然后建模上、下层决策目标、威胁规避与无人机性能约束并引入变长规划时间,进而设计基于双层决策的路径规划模型.规划过程中通过嵌入启发式优化策略来进一步改善路径的全局与局部平滑度,并提高路径搜索效率.大量复杂场景中的仿真及与现有经典方法的对比结果表明:该方法能够实时避开复杂危险区域,规划适合飞行的、较短的平滑路径.     

Path planning based on geographical features information for an autonomous mobile robot

We propose a path-planning algorithm for an autonomous mobile robot using geographical information, under the condition that the robot moves in an unknown environment. Images input by a camera at every sampling time are analyzed and geographical elements are recognized, and the geographical information is embedded in an environmental map. Then the path is updated by integrating the known information and the prediction on the unknown environment. We used a sensor fusion method to improve the mobile robot's dead-reckoning accuracy. The experimental results confirm the effectiveness of the proposed algorithm as the robot reached the goal successfully using the geographical information.     

基于行为协同和虚拟目标相结合的无人机实时航路规划

针对实时航路规划问题,综合考虑航路最优、平滑性、全局收敛性以及从威胁域的逃逸能力等限制时,还没有有效的规划算法.为此提出了一种基于行为协同和虚拟目标相结合的无人机实时航路规划方法.该方法将无人机的航路规划行为分为局部和全局行为:局部行为采用基于模糊控制的方法,用来实现威胁体规避;全局行为使用全局算法,通过全局目标和虚拟目标的切换实现了全局目标收敛和威胁域边界跟踪,然后通过模糊控制器对两种行为进行协同.最后通过分析、证明以及几种不同情形下的仿真表明该方法具有航路短、平滑和全局收敛的特点.     

Learning control in spatial coordinates for the path-following of autonomous vehicles

We prove the existence of a P-type (proportional-type) space-learning control, which, on the basis of a kinematic third order nonlinear model of an autonomous nonholonomic vehicle and by a proper choice of the proportional control gain, guarantees asymptotic tracking of planar curves whose uncertain curvature is L$L$-periodic in the curvilinear abscissa. The behavior of a human driver, who repetitively learns the correct action from the past experience in the space, is mathematically reproduced. A stability analysis is presented while simulation results demonstrate the effectiveness of the presented approach.     

考虑无线充电的无人机路径在线规划

近年来, 无人机在物流、通信、军事任务、灾害救援等领域中展现出了巨大的应用潜力, 然而无人机的续航 能力是制约其使用的重大因素, 在无线充电技术不断突破和发展的背景下, 本文基于深度强化学习方法, 提出了一 种考虑无线充电的无人机路径在线优化方法, 通过无线充电技术提高无人机的任务能力. 首先, 对无人机功耗模型 和无线充电模型进行了构建, 根据无人机的荷电状态约束, 设计了一种基于动态上下文向量的深度神经网络模型, 通过编码器和解码器的模型架构, 实现无人机路径的直接构造, 通过深度强化学习方法对模型进行离线训练, 从而 应用于考虑无线充电的无人机任务路径在线优化. 文本通过与传统优化方法和深度强化学习方法进行实验对比, 所提方法在CPU算力和GPU算力下分别实现了4倍以及100倍以上求解速度的提升.     

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.     

A comparison of optimization techniques for AUV path planning in environments with ocean currents

To date, a large number of optimization algorithms have been presented for Autonomous Underwater Vehicle (AUV) path planning. However, little effort has been devoted to compare these techniques. In this paper, an quantum-behaved particle swarm optimization (QPSO) algorithm is introduced for solving the optimal path planning problem of an AUV operating in environments with ocean currents. An extensive study of the most important optimization techniques applied to optimize the trajectory for an AUV in several test scenarios is presented. Extensive Monte Carlo trials were also run to analyse the performance of these optimization techniques based on solution quality and stability. The weaknesses and strengths of each technique have been stated and the most appropriate algorithm for AUV path planning has been determined.     

Heuristic collision-free path planning for an autonomous platform

In this paper, a heuristic and learning, algorithmic scheme for collision-free navigation is presented. This scheme determines an optimum collision-free navigation path of an autonomous platform by using a trial and error process, past navigation knowledge and current information extracted from the generated surrounding environment.     

A new model for path planning with interval data

In this paper, we establish a new model for path planning with interval data which arises in a variety of applications. It is formulated as minimum risk-sum path problem  : given a source-destination pair in a network G=(V,E)$G=(V,E)$, traveling on each link e in G   may take time _xe$x_e$ in a prespecified interval [_le,_ue]$[l_e,u_e]$ and take risk (_ue-_xe)/(_ue-_le)$(u_e-x_e)/(u_e-l_e)$, the goal is to find a path in G from the source to the destination, together with an allocation of travel times along each link on the path, so that the total travel time of links on the path is no more than a given time bound and the risk-sum over the links on the path is minimized. Our study shows that this new model has two features that make it different from the existing models. First, the minimum risk-sum path problem is polynomial-time solvable, and second, it provides many solutions that vary with time bounds and risk sums and leaves the choice for decision makers. Therefore, the new model is more flexible and easier to use for the path planning with interval data.     

Multiple-criterion shortest path algorithms for global path planning of unmanned combat vehicles

We consider a multiple-criterion shortest path problem with resource constraints, in which one needs to find paths between two points in a terrain for the movement of an unmanned combat vehicle (UCV). In the path planning problem considered here, cumulative traverse time of the UCV, risk level, and (communication) jamming level associated with the paths are limited to be less than or equal to given limits. We propose a modified label-correcting algorithm with a new label-selection strategy to find Pareto-optimal solutions for the multiple objectives of minimizing the traverse time, risk level, and jamming level related to the paths. In addition, we develop a path planning algorithm based on the label-correcting method to solve problems with a single objective within a reasonably short time. For evaluation of the performance of the proposed algorithms, computational experiments are performed on a number of instances, and results show that the proposed algorithms perform better than existing methods in terms of a computation time.     

基于滚动时域优化的无人飞行器轨迹规划

给出了寻求无人飞行器的最优轨迹的一种方法,其问题描述为使飞行器从初始状态飞行到目标状态,同时避免撞到障碍物。基于混合整数规划的滚动时域优化方法用来求解飞行器的轨迹规划问题。给出的仿真结果显示此方法的有效性以及在复杂环境下的可实时计算性。     

A multi-population immune plasma algorithm for path planning of unmanned combat aerial vehicle

Autonomous flight of an unmanned aerial vehicle (UAV) or its weaponized variant named unmanned combat aerial vehicle (UCAV) requires a route or path determined carefully by considering the optimization objectives about the enemy threats and fuel consumption of the system being operated. Immune Plasma algorithm (IP algorithm or IPA) is one of the most recent optimization techniques and directly models the fundamental steps of a medical method also used for the COVID-19 disease and known as convalescent or immune plasma treatment. In this study, IP algorithm for which a promising performance has already been validated with a single population was first extended to a multi-population domain supported by a migration schema. Moreover, the usage of the donor as a source of plasma for the treatment operations of a receiver was remodeled. The new variant of the IPA empowered with the multi-population and modified donor usage approach was called Multi-IP algorithm or MULIPA. For investigating the solving capabilities of the MULIPA as a UCAV path planner, different battlefield scenarios and algorithm specific parameter configurations were used. The results obtained by the MULIPA were compared with the results of other meta-heuristic based path planners. The comparative studies between MULIPA and other techniques showed that newly proposed IPA variant is capable of finding more secure and fuel efficient paths for a UCAV system.     

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.     

Cooperative path planning with priority target assignment and collision avoidance guidance for rescue unmanned surface vehicles in a complex ocean environment

In this paper, a novel cooperative path planning scheme of unmanned surface vehicles (USVs) for rescuing targets in a complex ocean environment is proposed. The primary objective of the rescue USVs is to bring all targets back safely on the premise of first rescuing priority targets, while optimizing the path length, the navigation time and the angular energy. The main contributions of this paper are as follows: (1) The proposed K-means-division (KMD) algorithm is able to identify a complex ocean environment with collision-free zone and static-obstacles zone; (2) The proposed path planning method with fast-marching-method-based ellipse guidance range (E-FMM) is able to optimize the angular energy while ensuring safety; (3) The proposed cooperative management system (including priority-target-assignment (PTA) with reward-mechanism genetic-optimization (RM-GO) and collision-avoidance (CA) guidance law with Tangent-based surge-varying wave-disturbances-observer (Tangent-SV-WDO)) can accomplish the mission of the rescue USVs. Comparative studies with the state-of-the-art methods demonstrate that the proposed cooperative path planning scheme is superior in terms of priority-target-assignment (PTA) and collision-avoidance (CA) of the actual rescue work.