多无人机空中加油的最优会合航路规划

为了空中加油能面向多架无人机,本文提出了空中加油的三维最优会合航路规划算法.多架无人机分布在不同区域,需要加油机沿预定的规划航路飞行会合,以完成空中加油任务.由于加油机可同时服务的受油机数量有限,需要寻找最优分配策略将无人机预分配至不同加油区域与之会合.本文首先根据加、受油机在各加油区域的最短会合时间,将最优分配问题建模为整数线性规划问题,求解得到加油机与各无人机的最优会合点.随后,本文提出了三维空间Dubins路径延长算法,保证各无人机按照分配结果与加油机同时到达会合点.最后,分别针对二维和三维多架无人机空中加油任务进行仿真.仿真结果表明本文提出的最优会合航路规划算法得到的Dubins航路,可以保证空中加油会合任务在最短时间内完成.     

Differential evolution and underwater glider path planning applied to the short-term opportunistic sampling of dynamic mesoscale ocean structures

This paper presents an approach where differential evolution is applied to underwater glider path planning. The objective of a glider is to reach a target location and gather research data along its path by propelling itself underwater and returning periodically to the surface. The main hypothesis of this work is that gliders operational capabilities will benefit from improved path planning, especially when dealing with opportunistic short-term missions focused on the sampling of dynamic structures. To model a glider trajectory, we evolve a global underwater glider path based on the local kinematic simulation of an underwater glider, considering the daily and hourly sea currents predictions. The global path is represented by control points where the glider is expected to resurface for communication with a satellite and to receive further navigation instructions. Some well known differential evolution instance algorithms are then assessed and compared on 12 test scenarios using the proposed approach. Finally, a real case glider vessel mission was commanded using this approach.     

能耗最优的水下滑翔机采样路径规划

研究了以能耗为优化准则的水下滑翔机海洋环境参数采样路径规划方法.首先,根据水下滑翔机的运动特点,建立了水下滑翔机采样作业过程的能耗模型;其次,基于能耗模型提出了一种能耗最小的滑翔运动参数优化方法,该方法避免了求解复杂的混合整数非线性规划问题;之后,在能耗最优的滑翔运动参数优化基础上,提出了一种基于两步链式Lin-Ker...     

Energy-optimal trajectory planning for car-like robots

When a battery-powered robot needs to operate for a long period of time, optimizing its energy consumption becomes critical. Driving motors are a major source of power consumption for mobile robots. In this paper, we study the problem of finding optimal paths and velocity profiles for car-like robots so as to minimize the energy consumed during motion. We start with an established model for energy consumption of DC motors. We first study the problem of finding the energy optimal velocity profiles, given a path for the robot. We present closed form solutions for the unconstrained case and for the case where there is a bound on maximum velocity. We then study a general problem of finding an energy optimal path along with a velocity profile, given a starting and goal position and orientation for the robot. Along the path, the instantaneous velocity of the robot may be bounded as a function of its turning radius, which in turn affects the energy consumption. Unlike minimum length paths, minimum energy paths may contain circular segments of varying radii. We show how to efficiently construct a graph which generalizes Dubins’ paths by including segments with arbitrary radii. Our algorithm uses the closed-form solution for the optimal velocity profiles as a subroutine to find the minimum energy trajectories, up to a fine discretization. We investigate the structure of energy-optimal paths and highlight instances where these paths deviate from the minimum length Dubins’ curves. In addition, we present a calibration method to find energy model parameters. Finally, we present results from experiments conducted on a custom-built robot for following optimal velocity profiles.     

Persistent ocean monitoring with underwater gliders: Adapting sampling resolution

Ocean processes are dynamic and complex and occur on multiple spatial and temporal scales. To obtain a synoptic view of such processes, ocean scientists collect data over long time periods. Historically, measurements were continually provided by fixed sensors, e.g., moorings, or gathered from ships. Recently, an increase in the utilization of autonomous underwater vehicles has enabled a more dynamic data acquisition approach. However, we still do not utilize the full capabilities of these vehicles. Here we present algorithms that produce persistent monitoring missions for underwater vehicles by balancing path following accuracy and sampling resolution for a given region of interest, which addresses a pressing need among ocean scientists to efficiently and effectively collect high‐value data. More specifically, this paper proposes a path planning algorithm and a speed control algorithm for underwater gliders, which together give informative trajectories for the glider to persistently monitor a patch of ocean. We optimize a cost function that blends two competing factors: maximize the information value along the path while minimizing deviation from the planned path due to ocean currents. Speed is controlled along the planned path by adjusting the pitch angle of the underwater glider, so that higher resolution samples are collected in areas of higher information value. The resulting paths are closed circuits that can be repeatedly traversed to collect long‐term ocean data in dynamic environments. The algorithms were tested during sea trials on an underwater glider operating off the coast of southern California, as well as in Monterey Bay, California. The experimental results show improvements in both data resolution and path reliability compared to previously executed sampling paths used in the respective regions. © 2011 Wiley Periodicals, Inc.     

基于Dubins路径的无人艇运动规划算法

针对无人艇运动规划问题,通过Dubins路径的理论分析,提出一种利用纯粹几何方法的Dubins路径计算方法。该方法中没有出现解方程组的运算,而是首先根据无人艇运动状态计算转向圆,然后利用几何方法计算转向圆间的公切线,最后通过公切线连接得到Dubins路径。通过5组仿真实验验证了所提方法的有效性。前4组仿真实验分别设计了计算Dubins路径过程中可能出现的各种情形,以验证算法适用于多种情况的Dubins路径计算。最后一组仿真实验用于无人艇的路径规划及运动状态调整,仿真结果表明,基于Dubins路径的无人艇运动规划算法是可行的。     

A hybrid strategy for the time- and energy-efficient trajectory planning of parallel platform manipulators

In planning the trajectories of motor-driven parallel platform manipulators, the objective is to identify the trajectory which accomplishes the assigned motion with the minimal travel time and energy expenditure subject to the constraints imposed by the kinematics and dynamics of the manipulator structure. In this study, the possible trajectories of the manipulator are modeled using a parametric path representation, and the optimal trajectory is then obtained using a hybrid scheme comprising the particle swarm optimization method and the local conjugate gradient method. The numerical results confirm the feasibility of the optimized trajectories and show that the hybrid scheme is not only more computationally efficient than the standalone particle swarm optimization method, but also yields solutions of a higher quality.     

On the Complete Coverage Path Planning for Mobile Robots

This paper presents a generalized complete coverage path planning (CCPP) algorithm and its implementation for a mobile robot. The proposed planner contains two concerns: 1) low working time or low energy consumption, and 2) high human safety. For the first concern, we design the optimal path by incorporating two factors: time and energy costs. Describing the working time and energy in terms of a turning parameter simplifies the optimal path design either for minimizing the time or energy cost. For obstacle avoidance in the CCPP, fixed or moving objects are avoided by proposing a field method describing the effects of factors such as working dangerousness and difficulty on the current robot navigation. The human safety is simultaneously guaranteed by this method. Furthermore, a backstepping controller considering constraints imposed on the control input is established to track the optimal route. An implementation of the proposed CCPP for the experimentally mobile robot equipped with this controller is presented; the verification results demonstrate significant performance and practicality of the proposed strategy.     

多圆碟形水下滑翔机的双层协调三维路径规划

本文研究了欠驱动圆碟形水下滑翔机集群在海流干扰和水下碍航物影响下的三维路径规划问题. 具体地: 第一, 根据圆碟形水下滑翔机的航行特点, 建立了相应的航行时间模型, 设计了三维路径规划的优化目标; 第二, 提 出了一种基于双层协调的多水下滑翔机三维路径规划结构, 采用基于三维离散空间的全局路径规划和基于人工势 场法的局部路径规划, 避免了滑翔机与碍航物以及不同优先级的滑翔机之间发生碰撞; 第三, 基于双层协调路径规 划结构, 采用基于量子行为的自适应粒子群优化方法完成了时间最优目标下多圆碟形水下滑翔机的三维路径规划. 仿真结果验证了所提多圆碟形水下滑翔机三维路径规划方法的有效性.     

基于Q学习的水下滑翔机路径规划方法

针对水下滑翔机路径规划问题，提出了一种基于Q学习的水下滑翔机路径规划方法。考虑到水下滑翔机在执行一些特定任务时会提前给定俯仰角及深度参数，且航向角选择范围通常是几个离散角度值，本文针对典型的几种俯仰角情况分别设计了航向动作选择集，这避免了Q学习方法“维数爆炸”问题。根据水下滑翔机航程最短的目标和障碍物外部约束条件，设计了奖励函数与动作选择策略。相较于传统路径规划方法，本文提出的方法不需要提前知道环境信息，而是在学习过程中根据环境的反馈选择最优动作，因此该方法在不同的环境条件下有优良的迁移能力。仿真结果表明，该方法能在未知环境中为水下滑翔机规划出规避障碍且航程短的路径。     

Classification of the Dubins set

Given two points in a plane, each with a prescribed direction of motion in it, the question being asked is to find the shortest smooth path of bounded curvature that joins them. The classical 1957 result by Dubins gives a sufficient set of paths (each consisting of circular arcs and straight line segments) which always contains the shortest path. The latter is then found by explicitly computing all paths on the list and then comparing them. This may become a problem in applications where computation time is critical, such as in real-time robot motion planning. Instead, the logical classification scheme considered in this work allows one to extract the shortest path from the Dubins set directly, without explicitly calculating the candidate paths. The approach is demonstrated on one of two possible cases that appear here — when the distance between the two points is relatively large (the case with short distances can be treated similarly). Besides computational savings, this result sheds light on the nature of factors affecting the length of paths in the Dubins problem, and is useful for further extensions, e.g. for finding the shortest path between a point and a manifold in the corresponding configuration space.     

Imperialist Competitive Algorithm for AUV Path Planning in a Variable Ocean

An imperialist competitive algorithm (ICA) is introduced for solving the optimal path planning problem for autonomous underwater vehicles (AUVs) operating in turbulent, cluttered, and uncertain environments. ICA is a new sociopolitically inspired global search metaheuristic based on a form of competition between “imperialist” forces and opposing colonies. In this study, ICA is applied to optimize the coordinates of a set of control points for generating a curved spline path. The ICA-based path planner is tested to find an optimal trajectory for an AUV navigating through a variable ocean environment in the presence of an irregularly shaped underwater terrain. The genetic algorithm (GA) and quantum-behaved particle swarm optimization (QPSO) are described and evaluated with the ICA for the path optimization problem. Simulation results show that the proposed ICA approach is able to obtain a more optimized trajectory than the GA- or QPSO-based methods. Monte Carlo simulations demonstrate the robustness and superiority of the proposed ICA scheme compared with the GA and QPSO schemes.     

Cellular ants: A method to create collision free trajectories for a cooperative robot team

Creating collision-free trajectories for mobile robots, known as the path planning problem, is considered to be one of the basic problems in robotics. In case of multiple robotic systems, the complexity of such systems increases proportionally with the number of robots, due to the fact that all robots must act as one unit to complete one composite task, such as retaining a specific formation. The proposed path planner employs a combination of Cellular Automata (CA) and Ant Colony Optimization (ACO) techniques in order to create collision-free trajectories for every robot of a team while their formation is kept immutable. The method reacts with obstacle distribution changes and therefore can be used in dynamical or unknown environments, without the need of a priori knowledge of the space. The team is divided into subgroups and all the desired pathways are created with the combined use of a CA path planner and an ACO algorithm. In case of lack of pheromones, paths are created using the CA path planner. Compared to other methods, the proposed method can create accurate collision-free paths in real time with low complexity while the implemented system is completely autonomous. A simulation environment was created to test the effectiveness of the applied CA rules and ACO principles. Moreover, the proposed method was implemented in a system using a real world simulation environment, called Webots. The CA and ACO combined algorithm was applied to a team of multiple simulated robots without the interference of a central control. Simulation and experimental results indicate that accurate collision free paths could be created with low complexity, confirming the robustness of the method.     

Stochastic automated search methods in cellular automata: the discovery of tens of thousands of glider guns

This paper deals with the spontaneous emergence of glider guns in cellular automata. An evolutionary search for glider guns with different parameters is described and other search techniques are also presented to provide a benchmark. We demonstrate the spontaneous emergence of an important number of novel glider guns discovered by an evolutionary algorithm. An automatic process to identify guns leads to a classification of glider guns that takes into account the number of emitted gliders of a specific type. We also show it is possible to discover guns for many other types of gliders. Significantly, all the found automata can be candidate to an automatic search for collision-based universal cellular automata simulating Turing machines in their space-time dynamics using gliders and glider guns.     

Motion Planning for Redundant Manipulators Using a Floating Point Genetic Algorithm

This paper deals with the trajectory planning problem for redundant manipulators. A genetic algorithm (GA) using a floating point representation is proposed to search for the optimal end-effector trajectory for a redundant manipulator. An evaluation function is defined based on multiple criteria, including the total displacement of the end-effector, the total angular displacement of all the joints, as well as the uniformity of Cartesian and joint space velocities. These criteria result in minimized, smooth end-effector motions. Simulations are carried out for path planning in free space and in a workspace with obstacles. Results demonstrate the effectiveness and capability of the proposed method in generating optimized collision-free trajectories.     

Time-space Viewpoint Planning for Guard Robot with Chance Constraint

This paper presents a novel movement planning algorithm for a guard robot in an indoor environment, imitating the job of human security. A movement planner is employed by the guard robot to continuously observe a certain person. This problem can be distinguished from the person following problem which continuously follows the object. Instead, the movement planner aims to reduce the movement and the energy while keeping the target person under its visibility. The proposed algorithm exploits the topological features of the environment to obtain a set of viewpoint candidates, and it is then optimized by a cost-based set covering problem. Both the robot and the target person are modeled using geodesic motion model which considers the environment shape. Subsequently, a particle model-based planner is employed, considering the chance constraints over the robot visibility, to choose an optimal action for the robot. Simulation results using 3D simulator and experiments on a real environment are provided to show the feasibility and effectiveness of our algorithm.

     

改进蚁群算法水面无人艇平滑路径规划

针对水面无人艇的路径规划,首先用仿生学算法对环境障碍物做开运算,提出改进的蚁群算法搜索可行路径得到航路点序列,优化合并没有障碍物的相邻航路点并顺序连接,得到可行且无碰撞风险的全局路径;其次,使用Dubins曲线算法对连接点进行平滑处理,分析其几何特性并找出其不足之处;最后,引入贝塞尔三阶曲线理论对于已经优化过的折线段进行平滑处理,使其在满足最小旋转半径的同时,也满足USV动力学特性,最终得到一条优化可行的路径.仿真结果证明本算法设计的光滑路径在计算复杂度、路径优化等方面都有了较大的提高.     

Heterogeneous-ants-based path planner for global path planning of mobile robot applications

Mobile robots can be applied to a wide range of problems, and the demand for these applications has risen in recent years, increasing interest in the study of mobile robotics. Many studies have examined the path planning problem, one of the most important issues in mobile robotics. However, the grid paths found by traditional planners are often not the true shortest paths or are not smooth because their potential headings are artificially constrained to multiples of 45 degrees. These paths are unfit for application to mobile robots because the high number of heading changes increases the energy required to move the mobile robot. Some studies have proposed a post-processing step to smooth the grid path. However, in this case, the post-smoothed path may not necessarily find the true shortest path because the post-smoothed path is still constrained to headings of multiples of 45 degrees. This study attempts to develop a global path planner that can directly find an optimal and smoother path without post-processing to smooth the path. We propose a heterogeneous-ants-based path planner (HAB-PP) as a global path planner to overcome the shortcomings mentioned above. The HAB-PP was created by modifying and optimizing the global path planning procedure from the ant colony optimization (ACO) algorithm. The proposed algorithm differs from the traditional ACO path planning algorithm in three respects: modified transition probability function for moving ants, modified pheromone update rule, and heterogeneous ants. The simulation results demonstrate the effectiveness of the HAB-PP.

     

Intelligent Coverage Path Planning for Agricultural Robots and Autonomous Machines on Three-Dimensional Terrain

Field operations should be done in a manner that minimizes time and travels over the field surface. Automated and intelligent path planning can help to find the best coverage path so that costs of various field operations can be minimized. The algorithms for generating an optimized field coverage pattern for a given 2D field has been investigated and reported. However, a great proportion of farms have rolling terrains, which have a considerable influence on the design of coverage paths. Coverage path planning in 3D space has a great potential to further optimize field operations and provide more precise navigation. Supplementary to that, energy consumption models were invoked taking into account terrain inclinations in order to provide the optimal driving direction for traversing the parallel field-work tracks and the optimal sequence for handling these tracks under the criterion of minimizing direct energy requirements. The reduced energy requirements and consequently the reduced emissions of atmospheric pollutants, e.g. CO₂ and NO, are of major concern due to their contribution to the greenhouse effect. Based on the results from two case study fields, it was shown that the reduction in the energy requirements when the driving angle is optimized by taking into account the 3D field terrain was 6.5 % as an average for all the examined scenarios compared to the case when the applied driving angle is optimized assuming even field terrain. Additional reduction is achieved when sequence of field tracks is optimized by taking into account inclinations for driving up and down steep hills.     

Integration of Path/Maneuver Planning in Complex Environments for Agile Maneuvering UCAVs

In this work, we consider the problem of generating agile maneuver profiles for Unmanned Combat Aerial Vehicles in 3D Complex environments. This problem is complicated by the fact that, generation of the dynamically and geometrically feasible flight trajectories for agile maneuver profiles requires search of nonlinear state space of the aircraft dynamics. This work suggests a two layer feasible trajectory/maneuver generation system. Integrated Path planning (considers geometrical, velocity and acceleration constraints) and maneuver generation (considers saturation envelope and attitude continuity constraints) system enables each layer to solve its own reduced order dimensional feasibility problem, thus simplifies the problem and improves the real time implement ability. In Trajectory Planning layer, to solve the time depended path planning problem of an unmanned combat aerial vehicles, we suggest a two step planner. In the first step, the planner explores the environment through a randomized reachability tree search using an approximate line segment model. The resulting connecting path is converted into flight way points through a line-of-sight segmentation. In the second step, every consecutive way points are connected with B-Spline curves and these curves are repaired probabilistically to obtain a geometrically and dynamically feasible path. This generated feasible path is turned in to time depended trajectory with using time scale factor considering the velocity and acceleration limits of the aircraft. Maneuver planning layer is constructed upon multi modal control framework, where the flight trajectories are decomposed to sequences of maneuver modes and associated parameters. Maneuver generation algorithm, makes use of mode transition rules and agility metric graphs to derive feasible maneuver parameters for each mode and overall sequence. Resulting integrated system; tested on simulations for 3D complex environments, gives satisfactory results and promises successful real time implementation.