Trajectory planning for multi robot systems: methods and Applications Overview reading notes

1.Introduction

In this paper Multi-Robot System (MRS) Not limited to robots , It means UAV and UGV
requirement ： Arrive at the designated place safely , Try to choose a short distance 、 short time

Introduces UAV and autopilot ：

1. UAV：3D path planning, To adjust the flight altitude , Factors such as weather and strong wind should be considered
2. UGV：2D, There are certain limitations , Because we can't cross obstacles like drones ; More autonomy , You can reach far places

2.Multi-robots systems

1. Definition ：Multi-Robot Systems includes all those groups formed by two or more robots sharing the same work space. （ Mechanical arm 、 Unmanned aerial vehicle (uav) 、 Autopilot and so on ）
2. Related terms ：
   ① Multi-Robot Systems： A system containing multiple robots , A very broad concept
   ② Multi-Agent System： Multiple intelligences that can interact with each other agent Composed system , It doesn't just belong to the field of robots , biology 、 Psychology and other fields also apply
   ③ Robotic Swarms： General and scalability , Communication between machines
   ④ Sensor Networks： Sensor networks
3. Control and decision making structure ：
   ① Centralized Architecture Centralized structure , Have a communication center , Communication will be affected by distance / Communication equipment , Once the center is destroyed , It's bad
   ②Decentralized Architecture Decentralized structure , It is divided into Distributed architecture or Hierarchy
4. homogeneous MRS All robots are the same , heterogeneous MRS There are different robots
   
5. agent The relationship between ：
   ① Indifference： Each is independent
   ② Cooperation： There is a common task
   ③ Competition or antagonism： Competition

3.Path Planning

（ The name of the review is clearly trajectory planning, But it's all about path planning）

1. Common terms ：
   ① Path-planning： Find a continuous way in C-space（free space & obstacle space）, It may not be smooth ; Focus on providing solutions （ Just find it , Don't ask for the best ） feasibility,Optimality
   ② Optimal Path Planning： Yes cost function, The cost function needs to be optimized
   ③ Trajectory Planning： Considering the dynamic characteristics of the vehicle , Speed 、 The acceleration
   

3.1. Decomposition graph-based methods

Decompose the environment into multiple meshes , Get the environment representation , Need to identify where to start 、 obstacle . It's equivalent to an undirected graph
that , The problem becomes Find a path from the initial node to the termination node

3.1.1. Dijkstra algorithm

dijkstra (Dijkstra) Algorithm is a typical shortest path algorithm , Used to calculate the shortest path from one node to another . Its main feature is Expand from the starting point to the outside ( Breadth first search ideas ), Until it reaches the end .

3.1.2. A* algorithm

A star Heuristic algorithm , The valuation function is added on the basis of breadth first
Considering the distance from the destination , So it's going to be a lot faster

1. Function for calculating node priority ：$f(n)=g(n)+h(n)$; Get rid of $h(n)$ It degenerates into Dijkstra Algorithm
2. $g(n)$ Is the node n The cost of distance from the starting point ,$h(n)$ Is the node n The cost of getting to the end （ Heuristic function ）
3. $h(n)$ In fact, it's just a guess , Because only when we really pass by can we know the real distance （ There are obstacles in the middle ）; Commonly used heuristic functions ： Manhattan distance （ Only move up, down, left and right ）、 Diagonal distance （ Allow to move in eight directions ）、 Euclid distance （ Allow to move in any direction ）

Path planning A* Algorithm - Alibaba cloud yunqi's article - You know

3.1.3. D* algorithm

Dynamic A star; and A* similar , But the consideration is Dynamic shortest path

1. Detect dynamic obstacles , Heuristic functions are also used
2. Same as A* Similar algorithm ,D-star Through one ** A priority queue is maintained （OpenList）** To search the path nodes in the scene , The difference is ,D* Do not start the search from the starting point , It starts with the target point （ Reverse search ）, By placing the target point at Openlist To start searching , Until the current position node of the robot leaves the queue （ Of course, if the state of a node in the middle changes dynamically , Need to find a new way , So it is a dynamic routing algorithm ）.

3.2 Sampling based methods

Random mapping based on environment , Sampling is based on nodes or cell Conduct
Just keep sampling , Keep expanding
classification ：① active method： Choose the best path ② passive method： Just generate the road network

3.2.1. Probabilistic Road Map (Passive)

Path planning : PRM Path planning algorithm (Probabilistic Roadmaps Random road map )

1. Random scatter , Remove obstacles
2. The most recent k Connect the dots , If there is an obstacle in the middle , Can't connect ; Get the likelihood probability roadmap
3. Use A* Algorithm to search

advantage ： Be able to explore three-dimensional space with low computational cost

3.2.2. Voronoi diagram (Passive)

1. Voronoi diagram The problem solved is actually based on A specific set of points divides the plane into different areas , And each area only contains a unique specific point , also The distance from any position in the area to the specific point is closer than that to other specific points .
2. Personal understanding ： There are a number of fixed points , We use an area to wrap each point , The distance between any point in the area and the fixed point All less than The arbitrary point is away from the fixed point in other areas .
   

3.2.3. Rapidly exploring random trees (Active)

RPT By randomly scattering points in the state space , Control the growth point and direction of the path tree ：

1. It is divided into free space and obstacle space, Set up start node and end node
2. Initialize a random node, Must be able to communicate with start node Connect , see end node Whether it can be connected , If so, it's over
3. If not , Generate random points again , It is required to be able to end Node connection

characteristic ：

1. Than RMP More directional
2. Non optimal solution
3. Low efficiency
4. Sample in the whole space

3.2.4. Artificial potential field methods (Active)

Artificial potential field method ： The influence of targets and obstacles on robot motion is embodied into Artificial potential field . The potential energy at the target is low , The potential energy at the obstacle is high .

Low computational complexity , But there is no guarantee of success , I don't know when I can succeed .

3.3. Mathematics model based methods

Method based on mathematical model , Establish dynamics and dynamic constraints , For modeling environments and systems .
Cost function to constrain .（ Not much information can be found on this part of the Internet ）

3.3.1. Mixed integer linear program

Mixed integer linear programming (MILP) Model ： be based on cost function , Considering Kinematic constraints 、 Minimum distance 、 Threats in energy or environment .

3.3.2. Mixed integer quadratic program

And MILP similar , However, it is necessary to perform the analysis of the target quadratic function

3.3.3. Optimal control

optimum control , From a set of differential equations state and path.

3.4. Bio-inspired methods

Simulate biological behavior , not being fully deterministic, presenting parallel structures, and being adaptive

3.4.1. Neuronal network

The related work：

1. CNN Analyze the environment ,DQN Generate action;
2. utilize MADDPG;
3. WoLFPHC (Win or Learn Fast Policy Hill-Climbing)： It solves the problem of slow learning 、 Difficult to learn in an unknown environment ; Each agent only saves its own actions to complete the learning task .
   WolF Refer to , When the agent does better than expected, carefully and slowly adjust the parameters , When the agent does worse than expected , Speed up the pace and adjust the parameters .
   PHC It is a single agent learning algorithm in a stable environment . The core of this algorithm is the idea of reinforcement learning , Increase the selection probability of the action that can get the maximum cumulative expectation . The algorithm is reasonable , Can converge to the optimal strategy . The algorithm flow is as follows
4. multi-layer architecture：Q-learning Determine the configuration of the vehicle ,PG Ensure no collision

3.4.2. Evolutionary algorithms

Based on random search , Such as ant colony algorithm 、 Genetic algorithms and so on

Table