当前位置:网站首页>Trajectory planning for multi robot systems: methods and Applications Overview reading notes
Trajectory planning for multi robot systems: methods and Applications Overview reading notes
2022-07-07 10:29:00 【strawberry47】
Catalog
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 :
- UAV:3D path planning, To adjust the flight altitude , Factors such as weather and strong wind should be considered
- 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
- 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 )
- 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 - 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 - homogeneous MRS All robots are the same , heterogeneous MRS There are different robots
- 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)
- 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
- Function for calculating node priority : f ( n ) = g ( n ) + h ( n ) f(n) = g(n)+h(n) f(n)=g(n)+h(n); Get rid of h ( n ) h(n) h(n) It degenerates into Dijkstra Algorithm
- g ( n ) g(n) g(n) Is the node n The cost of distance from the starting point , h ( n ) h(n) h(n) Is the node n The cost of getting to the end ( Heuristic function )
- h ( n ) h(n) 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
- Detect dynamic obstacles , Heuristic functions are also used
- 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 )
- Random scatter , Remove obstacles
- The most recent k Connect the dots , If there is an obstacle in the middle , Can't connect ; Get the likelihood probability roadmap
- Use A* Algorithm to search
advantage : Be able to explore three-dimensional space with low computational cost
3.2.2. Voronoi diagram (Passive)
- 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 .
- 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 :
- It is divided into free space and obstacle space, Set up start node and end node
- 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
- If not , Generate random points again , It is required to be able to end Node connection
characteristic :
- Than RMP More directional
- Non optimal solution
- Low efficiency
- 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:
- CNN Analyze the environment ,DQN Generate action;
- utilize MADDPG;
- 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 - 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
边栏推荐
- Factorial implementation of large integer classes
- IO模型复习
- Hdu-2196 tree DP learning notes
- Trajectory planning for multi-robot systems: Methods and applications 综述阅读笔记
- Postman interface test VI
- 1323:【例6.5】活动选择
- Appx code signing Guide
- SQLyog数据库怎么取消自动保存更改
- SolidWorks工程图中添加中心线和中心符号线的办法
- Kotlin realizes wechat interface switching (fragment exercise)
猜你喜欢
对word2vec的一些浅层理解
P2788 数学1(math1)- 加减算式
AHB bus in stm32_ Apb2 bus_ Apb1 bus what are these
[STM32] solution to the problem that SWD cannot recognize devices after STM32 burning program
【STM32】STM32烧录程序后SWD无法识别器件的问题解决方法
对存储过程进行加密和解密(SQL 2008/SQL 2012)
Pdf document signature Guide
[higherhrnet] higherhrnet detailed heat map regression code of higherhrnet
浅谈日志中的返回格式封装格式处理,异常处理
The story of Plato and his three disciples: how to find happiness? How to find the ideal partner?
随机推荐
电表远程抄表拉合闸操作命令指令
String formatting
浅谈日志中的返回格式封装格式处理,异常处理
Chris Lattner, père de llvm: Pourquoi reconstruire le logiciel d'infrastructure ai
Study summary of postgraduate entrance examination in August
【acwing】786. 第k个数
Multisim--软件相关使用技巧
Guid primary key
Easyexcel read write simple to use
JMeter installation
Leetcode-560: subarray with sum K
AHB bus in stm32_ Apb2 bus_ Apb1 bus what are these
Methods of adding centerlines and centerlines in SolidWorks drawings
OpenGL glLightfv 函数的应用以及光源的相关知识
Hdu-2196 tree DP learning notes
Socket通信原理和实践
2022.7.6DAY598
Why is the reflection efficiency low?
Factorial implementation of large integer classes
【STM32】STM32烧录程序后SWD无法识别器件的问题解决方法