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.     

Real time planning in N-dim state space

This paper presents the actual work in real-time planning as search [1] [2]. Based in this work we tried to solve the path planning in numerical state space. We found that precision, performance, and time were very linked. In real-time problem solving, the agent can fall in traps made of forbidden zones and to go out it, have to spend too much computing time. To solve this problem we propose a multilayer inference based in subgoals computation. An architecture based in two agents, one for low level task with the maximum precision and other for subgoals computation is proposed here.     

Real-Time Path Planning Algorithm for Autonomous Border Patrol: Design,Simulation, and Experimentation

This paper presents an online path planning algorithm for unmanned vehicles in charge of autonomous border patrol. In this Pursuit-Evasion game, the unmanned vehicle, acting as the pursuer, is required to capture multiple trespassers on its own before any of them reach a target safe house where they are safe from capture. The problem formulation is based on Isaacs’ Target Guarding problem, but extended to the case of multiple evaders. The proposed path planning method is based on Rapidly-exploring random trees (RRT) and is capable of producing trajectories within seconds to capture 2 or 3 evaders. Simulations are carried out to demonstrate that the resulting trajectories approach the optimal solution produced by a nonlinear programming-based numerical optimal control solver. Experiments are also conducted on unmanned ground vehicles to show the feasibility of implementing the proposed online path planning algorithm on physical applications.     

基于几何方法的多智能体群体刚性运动的路径规划

利用微分几何的方法在特殊欧氏群(Special Euclidean Group)上研究刚性运动.对于已知边界约束条件的多智能体群体刚性运动路径规划问题，采用了虚拟结构的模式；通过建立基于能量的最优准则，在特殊欧氏群上推导了多智能体协调运动的最优轨迹.所得到的最优轨迹是光滑的，而且与空间惯性坐标系的选择无关.该方法对于描述和规划多智能体的群体刚性运动具有广泛的适用性.     

Smooth and time‐optimal trajectory planning for industrial manipulators along specified paths

This article presents a method for determining smooth and time‐optimal path constrained trajectories for robotic manipulators and investigates the performance of these trajectories both through simulations and experiments. The desired smoothness of the trajectory is imposed through limits on the torque rates. The third derivative of the path parameter with respect to time, the pseudo‐jerk, is the controlled input. The limits on the actuator torques translate into state‐dependent limits on the pseudo‐acceleration. The time‐optimal control objective is cast as an optimization problem by using cubic splines to parametrize the state space trajectory. The optimization problem is solved using the flexible tolerance method. The experimental results presented show that the planned smooth trajectories provide superior feasible time‐optimal motion. © 2000 John Wiley & Sons, Inc.     

Real-time path planning in dynamic virtual environments using multiagent navigation graphs

We present a novel approach for efficient path planning and navigation of multiple virtual agents in complex dynamic scenes. We introduce a new data structure, Multi-agent Navigation Graph (MaNG), which is constructed using first- and second-order Voronoi diagrams. The MaNG is used to perform route planning and proximity computations for each agent in real time. Moreover, we use the path information and proximity relationships for local dynamics computation of each agent by extending a social force model [Helbing05]. We compute the MaNG using graphics hardware and present culling techniques to accelerate the computation. We also address undersampling issues and present techniques to improve the accuracy of our algorithm. Our algorithm is used for real-time multi-agent planning in pursuit-evasion, terrain exploration and crowd simulation scenarios consisting of hundreds of moving agents, each with a distinct goal.     

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.     

A framework of Voronoi diagram for planning multiple paths in free space

Most of the emphasis in path planning, a topic of much interest in several domains, has been on finding the optimal path or at most k optimal paths. However, in domains such as adversarial planning, one of the agents might deliberately take less optimal paths to confuse the opponent, and by the same token an agent, for inferring opponent's intent, has to consider all possible paths that the opponent might take. We introduce the notion of representative paths in free space (2D) and study the problem of computing all representative paths with different properties, such as all representative paths with at most L loops, among polygonal regions using a framework of Voronoi diagram. We prove three properties: (1) the upper and lower bounds to the number of simple paths in a Voronoi graph (2) given any path, a homotopic path can always be obtained from the Voronoi diagram of the regions and (3) all representative paths with a given property might not be always obtainable from the Voronoi graph even after searching the graph exhaustively and present an algorithm to work around this limitation. We also show how our findings can be applied for efficient entity re-identification, a problem involving a large number of dynamic entities and obstacles in the military domain.     

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

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

A Dirichlet–Neumann type algorithm for contact problems with friction

Domain decomposition techniques provide a powerful tool for the numerical approximation of partial differential equations. We introduce a new algorithm for the numerical solution of a nonlinear contact problem with Coulomb friction between linear elastic bodies. The discretization of the nonlinear problem is based on mortar techniques. We use a dual basis Lagrange multiplier space for the coupling of the different bodies. The boundary data transfer at the contact zone is essential for the algorithm. It is realized by a scaled mass matrix which results from the mortar discretization on non-matching triangulations. We apply a nonlinear block Gauss–Seidel method as iterative solver which can be interpreted as a Dirichlet–Neumann algorithm for the nonlinear problem. In each iteration step, we have to solve a linear Neumann problem and a nonlinear Signorini problem. The solution of the Signorini problem is realized in terms of monotone multigrid methods. Numerical results illustrate the performance of our approach in 2D and 3D. Received: 20 March 2001 / Accepted: 1 February 2002 Communicated by P. Deuflhard     

A hybrid cognitive/reactive intelligent agent autonomous path planning technique in a networked-distributed unstructured environment for reinforcement learning

This paper proposes a path planning technique for autonomous agent(s) located in an unstructured networked distributed environment, where each agent has limited and not complete knowledge of the environment. Each agent has only the knowledge available in the distributed memory of the computing node the agent is running on and the agents share some information learned over a distributed network. In particular, the environment is divided into several sectors with each sector located on a single separate distributed computing node. We consider hybrid reactive-cognitive agent(s) where we use autonomous agent motion planning that is based on the use of a potential field model accompanied by a reinforcement learning as well as boundary detection algorithms. Potential fields are used for fast convergence toward a path in a distributed environment while reenforcement learning is used to guarantee a variety of behavior and consistent convergence in a distributed environment. We show how the agent decision making process is enhanced by the combination of the two techniques in a distributed environment. Furthermore, path retracing is a challenging problem in a distributed environment, since the agent does not have complete knowledge of the environment. We propose a backtracking technique to keep the distributed agent informed all the time of its path information and step count including when migrating from one node to another. Note that no node has knowledge of the entire global path from a source to a goal when such a goal resides on a separate node. Each agent has only knowledge of a partial path (internal to a node) and related number of steps corresponding to the portion of the path that agent traversed when running on the node. In particular, we show how each of the agents(s), starting in one of the many sectors with no initial knowledge of the environment, using the proposed distributed technique, develops its intelligence based on its experience and seamlessly discovers the shortest global path to the target, which is located in a different node, while avoiding any obstacle(s) it encounters in its way, including when transitioning and migrating from one distributed computing node to another. The agent(s) use (s) multiple-token-ring message passing interface (MPI) to perform internode communication. Finally, the experimental results of the proposed method show that single and multiagents sharing the same goal and running on the same or different nodes successfully coordinate the sharing of their respective environment states/information to collaboratively perform their respective tasks. The results also show that distributed multiagent sharing information increases by an order of magnitude the speed of convergence to the optimal shortest path to the goal in comparison with the single-agent case or noninformation sharing multiagent case.     

Path deformation method for robot motion planning problems in the presence of obstacles

This paper studies the following path planning problem for a robot. There is a given path avoiding obstacles. If existing obstacles change their location or new obstacles appear, the preplanned path must be appropriately deformed for all obstacles avoidance. We develop a solution approach based on the component-wise method of smoothing the path curvature and the method of potentials. The proposed approach enables to avoid obstacles and smooth the path and its curvature (in the 2D and 3D cases).     

基于可满足性模理论求解器的程序路径验证方法

针对程序中因存在路径条数过多或复杂循环路径而导致路径验证时的路径搜索空间过大,直接影响验证的效率和准确率的问题,提出一种基于可满足性模理论（SMT）求解器的程序路径验证方法。首先利用决策树的方法对复杂循环路径提取不变式,构造无循环控制流图（NLCFG）;然后通过基本路径法对控制流图（CFG）进行遍历,提取基本路径信息;最后利用SMT求解器作为约束求解器,将路径验证问题转化为约束求解问题来进行处理。与同样基于SMT求解器的路径验证工具CBMC和FSoft-SMT相比,该方法在对测试集程序的验证时间上比CBMC降低了25%以上,比FSoft-SMT降低了15%以上;在验证精度上,该方法有明显的提升。实验结果表明,方法可以有效解决路径搜索空间过大的问题,同时提高路径验证的效率和准确率。     

EACS: Effective Avoidance Combination Strategy

When navigating in crowds, humans are able to move efficiently between people. They look ahead to know which path would reduce the complexity of their interactions with others. Current navigation systems for virtual agents consider long‐term planning to find a path in the static environment and short‐term reactions to avoid collisions with close obstacles. Recently some mid‐term considerations have been added to avoid high density areas. However, there is no mid‐term planning among static and dynamic obstacles that would enable the agent to look ahead and avoid difficult paths or find easy ones as humans do. In this paper, we present a system for such mid‐term planning. This system is added to the navigation process between pathfinding and local avoidance to improve the navigation of virtual agents. We show the capacities of such a system using several case studies. Finally we use an energy criterion to compare trajectories computed with and without the mid‐term planning.     

Two algorithms for a reachability problem in one-dimensional space

Two algorithms are proposed to solve a reachability problem among time-dependent obstacles in 1D space. In the first approach, the motion planning problem is reduced to a path existence problem in a directed graph. The algorithm is very simple, with running time O(n²), where n is the complexity of obstacles in space-time. The second algorithm uses a sweep-line technique and has running time O(n log₂ n). Besides, the latter algorithm can be easily modified to compute a collision-free trajectory, if such trajectories exist     

Dynamically-Stable Motion Planning for Humanoid Robots

We present an approach to path planning for humanoid robots that computes dynamically-stable, collision-free trajectories from full-body posture goals. Given a geometric model of the environment and a statically-stable desired posture, we search the configuration space of the robot for a collision-free path that simultaneously satisfies dynamic balance constraints. We adapt existing randomized path planning techniques by imposing balance constraints on incremental search motions in order to maintain the overall dynamic stability of the final path. A dynamics filtering function that constrains the ZMP (zero moment point) trajectory is used as a post-processing step to transform statically-stable, collision-free paths into dynamically-stable, collision-free trajectories for the entire body. Although we have focused our experiments on biped robots with a humanoid shape, the method generally applies to any robot subject to balance constraints (legged or not). The algorithm is presented along with computed examples using both simulated and real humanoid robots.     

基于深度强化学习的三维路径规划算法

合理的路线选择是智能体三维路径规划研究领域的难点。现有路径规划方法存在不能很好地适应未知地形,避障形式单一等问题。针对这些问题,提出了一种基于LSTM-PPO的智能体三维路径规划算法。利用虚拟射线探测仿真环境,并将收集到的状态空间和动作状态引入长短时记忆网络。通过额外的奖惩函数和好奇心驱动让智能体学会跳跃通过低矮障碍物,避开大型障碍物。利用PPO算法的截断项机制使得规划策略更新的幅度更加优化。实验结果表明,该算法是可行的,能够更加智能合理地选择路线,很好地适应存在多样障碍物的未知环境。     

Robotic Motion Using Harmonic Functions and Finite Elements

The harmonic functions have proved to be a powerful technique for motion planning in a known environment. They have two important properties: given an initial point and an objective in a connected domain, a unique path exists between those points. This path is the maximum gradient path of the harmonic function that begins in the initial point and ends in the goal point. The second property is that the harmonic function cannot have local minima in the interior of the domain (the objective point is considered as a border). This paper proposes a new method to solve Laplace’s equation. The harmonic function solution with mixed boundary conditions provides paths that verify the smoothness and safety considerations required for mobile robot path planning. The proposed approach uses the Finite Elements Method to solve Laplace’s equation, and this allows us to deal with complicated shapes of obstacles and walls. Mixed boundary conditions are applied to the harmonic function to improve the quality of the trajectories. In this way, the trajectories are smooth, avoiding the corners of walls and obstacles, and the potential slope is not too small, avoiding the difficulty of the numerical calculus of the trajectory. Results show that this method is able to deal with moving obstacles, and even for non-holonomic vehicles. The proposed method can be generalized to 3D or more dimensions and it can be used to move robot manipulators.     

A Generalized Real-Time Obstacle Avoidance Method Without the Cspace Calculation

An important concept proposed in the early stage of robot path planning field is the shrinking of a robot to a point and meanwhile the expanding of obstacles in the workspace as a set of new obstacles. The resulting grown obstacles are called the Configuration Space (Cspace) obstacles. The find-path problem is then transformed into that of finding a collision-free path for a point robot among the Cspace obstacles. However, the research experiences have shown that the Cspace transform is very hard when the following situations occur: 1) both the robot and obstacles are not polygons, and 2) the robot is allowed to rotate. This situation gets even worse when the robot and obstacles are three dimensional (3D) objects with various shapes. For this reason, direct path planning approaches without the Cspace transformation is quite useful and expected.Motivated by the practical requirements of robot path planning, a generalized constrained optimization problem (GCOP) with not only logic AND but also logic OR relationships was proposed and a mathematical solution developed previously. This paper inherits the fundamental ideas of inequality and optimization techniques from the previous work, converts the obstacle avoidance problem into a semi-infinite constrained optimization problem with the help of the mathematical transformation, and proposes a direct path planning approach without Cspace calculation, which is quite different from traditional methods. To show its merits, simulation results in 3D space have been presented.     

Formulation and optimization of cubic polynomial joint trajectories for industrial robots

Because of physical constraints, the optimum control of industrial robots is a difficult problem. An alternative approach is to divide the problem into two parts: optimum path planning for off-line processing followed by on-line path tracking. The path tracking can be achieved by adopting the existing approach. The path planning is done at the joint level. Cubic spline functions are used for constructing joint trajectories for industrial robots. The motion of the robot is specified by a sequence of Cartesian knots, i.e., positions and orientations of the hand. For anN-joint robot, these Cartesian knots are transformed intoNsets of joint displacements, with one set for each joint. Piecewise cubic polynomials are used to fit the sequence of joint displacements for each of theNjoints. Because of the use of the cubic spline function idea, there are onlyn - 2equations to be solved for each joint, wherenis the number of selected knots. The problem is proved to be uniquely solvable. An algorithm is developed to schedule the time intervals between each pair of adjacent knots such that the total traveling time is minimized subject to the physical constraints on joint velocities, accelerations, and jerks. Fortran programs have been written to implement: 1) the procedure for constructing the cubic polynomial joint trajectories; and 2) the algorithm for minimizing the traveling time. Results are illustrated by means of a numerical example.