why should we do this when searching free cell

[pengjiawei]

i have a little bit of confusion about line 61 in frontier_search.cpp
map_[nbr] <= map_[idx]
We have found the variable idx ,it is the FREE_SPACE that is nearest to the start. nbr is the nhood4 for idx.
On my opinion.it should be map_[nbr] < INSCRIBED_INFLATED_OBSTACLE not map_[nbr] <= map_[idx]
if we wanna search the free cell from the idx,because the cost values between 0 to 253 is free,is that right?
I am not sure,I am looking forward to your reply,thank you !

[zwkcoding]

Did you see the wiki about costmap_2d here?
map_[nbr] < INSCRIBED_INFLATED_OBSTACLE doesn't mean these positions are absolutely safe, it maybe in collision.
In my opinion, map_[nbr] <= map_[idx] could be replaced with FREE_SPACE == map_[nbr], here, the intention is to find the absolutely safe area.
If I am wrong, please point it out directly ;) @pengjiawei

[paulbovbel]

There's a two 'features' at play here, both existing to enable frontier search even when the 'initial' search cell is not strictly FREE_SPACE.

https://github.com/paulbovbel/frontier_exploration/blob/lunar-devel/src/frontier_search.cpp#L47 tries to find a clear cell nearby to start the search.

https://github.com/paulbovbel/frontier_exploration/blob/lunar-devel/src/frontier_search.cpp#L62 will always expand the breadth-first-search to neighbour cells that are cheaper or equal cost. This prevents the search from climbing into higher-cost areas, but has the (potential) downside of sidling along a non-zero-cost ledge around the starting point if necessary.

I would be open to providing a flag to disable one or both of these features, but they are still very necessary to frontier-search in non-optimal conditions.

[zwkcoding]

Good! thanks for fast and kind reply :)
I learnt the breath-first-search from your code ,Cuz you used it not only in finding frontier area but also in planning for a feasible path from start position to destination position :)
Thanks again. @paulbovbel
By the way, I want to ask a question: Is breath-first-search algorithm used in blob-detection which was referred in Yamauchi's paper to find the frontier?

[pengjiawei]

@zwkcoding yes,you're right the cost value that is less than INSCRIBED_INFLATED_OBSTACLE is not safe.I have found this and then I change the map_[nbr] < INSCRIBED_INFLATED_OBSTACLE to map_[nbr] < 128 according to this costmapspec.png , the cost value less than 128 means the distance betweens the robot and obstacles is above circumsribed_radius.it is strictly safe,is that right . I am not sure , thank you for your reply

[pengjiawei]

@paulbovbel thank you for your reply! But on my opinion, the performance breath-first-search algorithm is not ideal when the costmap updates it's values with inflation_layer . when my robot try to go through the narrow area , the bfs can't found frontiers because the cost value == FREE_SPACE are very few and surrounded by the cost value between 0 to 253 . the bfs will not climbing into higher-cost areas ,so I didn't find a solution

when I change the https://github.com/paulbovbel/frontier_exploration/blob/lunar-devel/src/frontier_search.cpp#L62 to map_[nbr] < 128 , it is not optimal and consumes a lot of resources but it can find a solution finally. I'm truly grateful for your help