author ： 19 the lz

The paper ：《FUEL: Fast UAV Exploration using Incremental Frontier Structure and Hierarchical Planning》

problem :

(a) The existing independent exploration methods lack effective global coverage 、 Conservative exercise plan and low decision-making frequency .
(b) Many existing autonomous exploration methods explore motion in a greedy way , For example, maximize instant messaging gain , Or navigate to the nearest unknown area . Greedy strategy ignores the global optimality , This leads to overall inefficiency .
Besides , Most methods produce fairly conservative movements , To ensure both information gain and security in previously unknown environments . Low exploration speed .
(d) Last but not least , Many methods are computationally expensive , And can't respond to environmental changes quickly and frequently . However , In order to achieve faster exploration , As long as new environmental information is available , A new campaign needs to be planned immediately .

contribution :

1. Incrementally updated FIS(frontier information structure), It captures the basic information of the whole exploration space and promotes high-frequency exploration programs .
2. A stratification ​​ Planning method , It can generate efficient global coverage path , And safe and agile local maneuvers for high-speed exploration .
   
   
   
   

Research process and results ：

Top ： Detect and remove obsolete boundaries .
Bottom ： New boundary detected （ Left ） And implement PCA, The large cluster is divided into two smaller clusters （ Right ）.

Red Bm Is the of the updated boundary area AABB box (axis-aligned bounding box/ Axis alignment bounding box ).
Every time the map is updated by sensor measurement , Update area Bm Of AABB(axis-aligned bounding box/ Axis alignment bounding box ) It will be recorded , Delete outdated boundary clusters and search for new boundary clusters .
Specific process :
1. Traverse all boundary clusters , return Bi And Bm The point of intersection .
2. Perform an accurate check on the returned cluster , Clusters that contain elements that no longer belong to boundary units will be deleted

After removing , New boundaries are searched by region growth algorithm and clustered into groups .
In these groups , The noise generated by sensor observation is usually ignored (cell Less ).
However , The remaining groups may contain large clusters , It is not conducive to distinguish unique unknown areas and make detailed decisions . therefore , We perform principal component analysis for each cluster (PCA), If the maximum eigenvalue exceeds the threshold , Then it is divided into two unified clusters along the first axis . Splitting is done recursively , In order to divide all large clusters into small clusters .

Generate candidate viewpoints for frontier clusters . In the cylindrical coordinate system centered on the average position of the cluster , Points are evenly sampled . For each sampling point located in free space p, Determine the angle to maximize sensor coverage to the cluster .

tlb(xk1,j1, xk2,j2) Expressed in two viewpoints xk1,j1 and xk2,j2 The lower bound of time when moving between
vmax and ˙ξmax Is the limit of yaw speed and angular rate

Step generate exploration motion ：
(1) Overall planning : Find the shortest path covering the leading-edge cluster in the whole environment ( Travel agent problem ).
( Asymmetric TSP: The optimal open-loop loop loop is obtained by finding the optimal closed-loop loop loop and retrieving its equivalent open-loop loop loop )

(2) Local improvement : Refine the global segment .

The global tourism plan has found a promising sequence of visits to all clusters . For all that , It only involves a single viewpoint of each cluster , This is not necessarily the best combination of all viewpoints .
So the local provides more viewpoints to consider
utilize Dijkstra Algorithms to minimize costs

(3) Minimum time B Spline trajectory : Generate a safe shortest time trajectory to the first viewpoint of the refinement tour .

Further optimization B All parameters of the spline , This minimizes the total trajectory time
Balance smoothness and overall time , And ensure safety and movement

experimental result

The average time of each part of the algorithm

Comparison of different algorithm paths

conclusion

The hierarchical planner plans the exploration movement in three consecutive steps , Find a valid global path , Select a set of local optimal viewpoints , And generate the shortest time local trajectory .

Running results