0
3. FrontierSearch算法
source link: https://charon-cheung.github.io/2022/05/04/%E8%B7%AF%E5%BE%84%E8%A7%84%E5%88%92/frontier-based%20exploration/3.%20FrontierSearch/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
3. FrontierSearch算法
Toggle site
Catalog
You've read100%
3. FrontierSearch算法
先找到离机器人所在栅格最近的空闲栅格，其索引为idx，再找它周围的4个邻居，分两种情况处理：
如果是未访问的空闲栅格
nbr，标记为已访问，插入队列A。依次递推，找出nbr的4个邻居，再把未访问的空闲栅格加入队列A如果这个4个邻居里有
frontier cell(未被访问，NO_INFORMATION而且至少有1个邻居是空闲栅格)，再检查这个frontier cell的8个邻居是否也有frontier，依次递推，从一个frontier寻找新的frontier，把所有frontier的个数和坐标记下来，求出形心坐标和机器人到每个frontier的距离distance，并逐次更新min_distance参数。 把符合条件的frontier加入列表frontier_list，对其中的frontier按照cost进行从小到大排序，最后返回frontier_list。
中间的紫色栅格是开始栅格idx，它的邻居1,2,3,4都是空闲栅格.从1开始寻找它的4个邻居，其中包括了5，1没有邻居是frontier。在下次循环处理2，它的邻居里也有5，这里就用到了访问标记，否则就会把5添加到队列A两次。 在访问4的邻居里就会找到frontier，寻找frontier时会用到另一个访问标记，逻辑也是一样的。
在上层的explore.cpp里寻找frontier时，找到的是cost最小的frontier，因为返回的frontier_list已经排好序。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK