# Proximal Operators for Multi-Agent Path Planning

@article{Bento2015ProximalOF, title={Proximal Operators for Multi-Agent Path Planning}, author={Jos{\'e} Bento and Nate Derbinsky and C. Mathy and J. Yedidia}, journal={ArXiv}, year={2015}, volume={abs/1504.01783} }

We address the problem of planning collision-free paths for multiple agents using optimization methods known as proximal algorithms. Recently this approach was explored in Bento et al. 2013, which demonstrated its ease of parallelization and decentralization, the speed with which the algorithms generate good quality solutions, and its ability to incorporate different proximal operators, each ensuring that paths satisfy a desired property. Unfortunately, the operators derived only apply to paths… Expand

#### Figures and Topics from this paper

#### 13 Citations

SPARTA : Fast global planning of collision-avoiding robot trajectories

- 2015

We present an algorithm for obtaining collision-avoiding robot trajectories we call SPARTA (SPline-based ADMM for Robot Trajectory Avoidance). We break the problem of solving for collision-avoiding… Expand

Improved Ant Colony Algorithms for Multi-agent Path Planning in Web3D Environment

- Computer Science
- 2017

Two kinds of ant colony algorithms and a leader idea to solve the path planning in 3D large-scale scenes are improved and a concept of vertebral visual area is put forward, which accelerates the speed of path finding in looking for the next node locked area. Expand

Resolving Spatial-Time Conflicts In A Set Of Any-angle Or Angle-constrained Grid Paths

- Computer Science
- ArXiv
- 2016

This work proposes an algorithm that eliminates conflicts by using local re-planning and introducing time offsets to the execution of paths by different agents, which can find high quality conflict-free solutions at low computational cost. Expand

IFC-based Improved ACO for Multi-agent Path Planning in Web3D Mountain Environment

- Computer Science, Engineering
- ICCAE '17
- 2017

A kind of method using an improved ant colony algorithm to find path for multi-agent in Web3D environment using HTML5 and an improved leader-follower method is used to organize the Blue army soldiers to attach the Red army soldiers. Expand

SI-Based mACO Multi-Agent Path Planning in Web3D Mountain Battle Scenes

- Computer Science
- 2016 International Conference on Virtual Reality and Visualization (ICVRV)
- 2016

A series of solutions proposed inhere: abstracting the mountain information including ray stone, round wood, entrenchment, bamboo nails trap and the fire power semantic information, then mapping every weapon's destruction value into every mountain terrain and use the value to compute the pheromones, which will be reused in the process of path planning. Expand

m2ACO: Multi-agent Path Planning Algorithm for Web3D Mountain Scenario

- Computer Science
- 2017

The paper proposed an m2ACO (multi-agent in mountain environment using ACO) algorithm for multi-agent path planning in Web3D technology and the experimental results show that the m2 ACO is more accurate than the other kinds of path planning algorithms. Expand

Distributed Optimization, Averaging via ADMM, and Network Topology

- Computer Science, Mathematics
- Proceedings of the IEEE
- 2020

Different algorithms when applied to a canonical distributed averaging consensus problem are compared and interesting connections between ADMM and the lifted Markov chains are shown besides providing an explicit characterization of its convergence and optimal parameter tuning in terms of spectral properties of the network. Expand

Efficient Projection onto the Perfect Phylogeny Model

- Computer Science
- NeurIPS
- 2018

This paper uses Moreau's decomposition for proximal operators, and a tree reduction scheme, to develop a new algorithm to compute a projection problem that assigns a fitness cost to phylogenetic trees. Expand

Efficient Projection onto the Perfect Phylogeny Model

- 2018

Several algorithms build on the perfect phylogeny model to infer evolutionary trees. This problem is particularly hard when evolutionary trees are inferred from the fraction of genomes that have… Expand

Efficient Projection onto the Perfect Phylogeny Model

- 2018

Several algorithms build on the perfect phylogeny model to infer evolutionary trees. This problem is particularly hard when evolutionary trees are inferred from the fraction of genomes that have… Expand

#### References

SHOWING 1-10 OF 38 REFERENCES

A message-passing algorithm for multi-agent trajectory planning

- Computer Science, Mathematics
- NIPS
- 2013

A novel approach for computing collision-free global trajectories for p agents with specified initial and final configurations, based on an improved version of the alternating direction method of multipliers (ADMM), which allows for incorporating different cost functionals with only minor adjustments. Expand

Collision avoidance for multiple agents with joint utility maximization

- Engineering
- ICRA 2013
- 2013

In this paper a centralized method for collision avoidance among multiple agents is presented. It builds on the velocity obstacle (VO) concept and its extensions to arbitrary kino-dynamics and is… Expand

The Increasing Cost Tree Search for Optimal Multi-Agent Pathfinding

- Mathematics, Computer Science
- IJCAI
- 2011

A number of optional pruning techniques that can significantly speed up the goal test of ICTS, the novel two-level search algorithm framework for multiple agents, are introduced. Expand

Randomized preprocessing of configuration for fast path planning

- Computer Science
- Proceedings of the 1994 IEEE International Conference on Robotics and Automation
- 1994

This paper presents a new approach to path planning for robots with many degrees of freedom (DOF) operating in known static environments that is particularly attractive for many-DOF robots which have to perform many successive point-to-point motions in the same environment. Expand

Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces

- 1996

Real-time robot motion planning using rasterizing computer graphics hardware. In Proc. OY82] C. O'D unlaing and C.K. Yap. A retraction method for planning the motion of a disc. A local approach for… Expand

Complete Algorithms for Cooperative Pathfinding Problems

- Computer Science
- IJCAI
- 2011

This work presents the first complete algorithm for finding cooperative pathfinding paths that is sufficiently fast for real-time applications and offers a trade-off between running time and solution quality. Expand

Distributed multi-robot task assignment and formation control

- Computer Science
- 2008 IEEE International Conference on Robotics and Automation
- 2008

This work addresses the challenge of distributed task assignment for multiple agents using market-based coordination protocols where the agents are able to bid for task assignment with the assumption that every agent has knowledge of the maximum number of agents that any given task can accommodate. Expand

The increasing cost tree search for optimal multi-agent pathfinding

- Mathematics, Computer Science
- Artif. Intell.
- 2011

This work presents a novel formalization for the problem of optimal pathfinding for multiple agents which includes a search tree called the increasing cost tree (ICT) and a corresponding search algorithm, called the increase cost tree search (ICTS) that finds optimal solutions. Expand

Motion Planning in Dynamic Environments Using Velocity Obstacles

- Computer Science, Mathematics
- Int. J. Robotics Res.
- 1998

This paper presents a method for robot motion planning in dynamic environments. It consists of selecting avoidance maneuvers to avoid static and moving obstacles in the velocity space, based on the… Expand

Incremental Sampling-based Algorithms for Optimal Motion Planning

- Computer Science
- Robotics: Science and Systems
- 2010

A new algorithm is considered, called the Rapidly-exploring Random Graph (RRG), and it is shown that the cost of the best path returned by RRG converges to the optimum almost surely, and a tree version of RRG is introduced, called RRT∗, which preserves the asymptotic optimality ofRRG while maintaining a tree structure like RRT. Expand