Finding Coordinated Paths for Multiple Holonomic Agents in 2-d Polygonal Environment
8
Citation
7
Reference
10
Related Paper
Citation Trend
Abstract:
Avoiding collisions is one of the vital tasks for systems of autonomous mobile agents. We focus on the problem of finding continuous coordinated paths for multiple mobile disc agents in a 2-d environment with polygonal obstacles. The problem is PSPACE-hard, with the state space growing exponentially in the number of agents. Therefore, the state of the art methods include mainly reactive techniques and sampling-based iterative algorithms. We compare the performance of a widely-used reactive method ORCA with three variants of a popular planning algorithm RRT* applied to multi-agent path planning and find that an algorithm combining reactive collision avoidance and RRT* planning, which we call ORCA-RRT* can be used to solve instances that are out of the reach of either of the techniques. We experimentally show that: 1) the reactive part of the algorithm can efficiently solve many multi-agent path finding problems involving large number of agents, for which RRT* algorithm is often unable to find a solution in limited time and 2) the planning component of the algorithm is able to solve many instances containing local minima, where reactive techniques typically fail.Keywords:
Maxima and minima
Holonomic
Online path planning is a crucial technology for aircraft flying in dynamic environments, no matter for safety or for precision target tracking. Fast planning algorithm is keystone for online path planning. New online path planning method based on path network combining with A* searching method was proposed in this paper. Fast Marching Method (FMM) is used to construct the path network for static environment, and the path segment can be reused once it was obtained, therefore, the replanning speed improved. Experiment showed that it works efficient for moving target tracking and pop-up obstacle avoidance.
Any-angle path planning
Obstacle avoidance
Fast marching method
Tracking (education)
Fast path
Cite
Citations (0)
An improved artificial potential field (IAPF) algorithm is proposed in this paper to promote the path planning characteristics of autonomous underwater vehicle (AUV). There are two critical problems restricting the application of obstacle avoidance path planning for the artificial potential field (APF) algorithm, one is the local minima and the other is the target unreachability problem. Therefore, the distance between the target and the AUV in attractive field is introduced into the repulsive potential field to modify the repulsive force so as to solve the problem of target unreachability. Moreover, an additional force is added to the resultant force to break the equilibrium when the local minima situation occurs. Ultimately, the simulation experiment validates that the improved artificial potential field method is an efficient way to realize the path planning for AUV in 3D space.
Maxima and minima
Potential field
Obstacle avoidance
Force Field
Cite
Citations (1)
This paper proposes a modified spatio-temporal A* path planning algorithm for the trajectory planning of mobile robots with non-holonomic constraints. Most path planning algorithms treat mobile robots as to be with holonomic constraints. However, wheeled mobile robots are affected by non-holonomic constraints, which leads to trajectory unreachability. To solve this problem, an improved spatio-temporal A* algorithm based on non-holonomic constraints is given, which considers the efficiency, completeness and smoothness of the path. At the same time, by improving the construction form of collision constraint and adding spatio-temporal constraints to the path, the success rate and solving speed of the path planning algorithm for non-holonomic constrained mobile robot are increased. Finally, simulation experiments are given to indicate that the proposed planning algorithm provides an optimized path, while improving the planning success rate and reducing the computational time.
Holonomic
Holonomic constraints
Cite
Citations (0)
Path planning is one of the most important parts in the research on flexible needle insertion. Based on the Improved Rapidly-exploring Random Tree (I-RRT), the path planning for flexible needle insertion is studied in this paper. Traditional RRT algorithm can generate paths which can avoid obstacle and reach the target precisely, but the path is not continuously differentiable and cannot match the physical constraints of the flexible needle inserting into soft tissue. Aiming at solving this problem, the I-RRT algorithm is proposed to generate paths for minimally invasive treatment and meanwhile guarantee the continuity and effectiveness of the path. The path evaluation function is designed to implement path selection based on path length, obstacle avoidance and the number of arcs. Then the simulation of the flexible needle path is performed in the environment with obstacles. Results show that the I-RRT is more practical and effective for flexible needle insertion path planning.
Random tree
Tree (set theory)
Path length
Any-angle path planning
Obstacle avoidance
Fast path
Cite
Citations (8)
This paper presents an adaptive artificial potential field method for robot's obstacle avoidance path planning. Despite the obstacle avoidance path planning based on the artificial potential field method is very popular, but there is local minima problem with this approach. As a result, this paper proposes an improved obstacle potential field function model considering for the size of the robot and the obstacles and changes the weight of the obstacle potential field function adaptively to make the robot escape from the local minima. Three simulations have been done and the simulation results show: the improved algorithm can make the robot escape from the local minima and accomplish the robot collision avoidance path planning well.
Maxima and minima
Obstacle avoidance
Potential field
Cite
Citations (57)
This paper gives concept of covering path planning, its mathematics description as well as its designing method about full covering path planning. The paper also describes several kinds of performance functions of covering path motion. According to this, we design a full covering path planner based on sequence of elementary motion with synthetical performance function.
Any-angle path planning
Planner
Sequence (biology)
Feature (linguistics)
Cite
Citations (1)
Aiming at the path planning of flexible needle,this paper comprehensively and systematically concluded the research status of the path planning.Due to the characteristics of needle puncture paths,we defined five different styles of paths.The path planners are defined and classified by path dimensions,path styles,planning directions and planning algorithms.Then we particularly summed up the realizations and characteristics of the four planning algorithms.Finally,we proposed the existing problems and the future trends of path panning for the flexible needle.
Panning (audio)
Any-angle path planning
Path length
Cite
Citations (2)
Holonomic
Planner
Tree (set theory)
Random tree
Section (typography)
Cite
Citations (5)
Abstract The article presents methods for constructing an unmanned vehicle (UV) motion path in an environment with obstacles to solve the problem of finding a path for a non-holonomic vehicle in an environment with obstacles. A combined approach is described and individual components are considered that allow solving the problem of planning a path for a non-holonomic vehicle. The practical use example of the combined approach for solving the problem of planning the UV path is given.
Holonomic
Cite
Citations (2)
The artificial potential field methods provide simple and effective motion planners for practical purposes. However, there is a major problem with the artificial potential field approach. It is the formation of local minima that can trap the robot before reaching its goal. The avoidance of local minima has been an active research topic in potential field path planning. As one of the powerful techniques for escaping local minima, simulated annealing has been applied to local and global path planning. In this paper, the authors present and apply the mobile robot path planning technique which integrate the artificial potential field approach with simulated annealing to mobile robots.
Maxima and minima
Obstacle avoidance
Potential field
Cite
Citations (143)