Your goal in this task will be to implement detection of frontiers in an occupancy grid. See template in aro_frontier in aro_frontier.zip package and below for explanation of occupancy grid. The aro_msgs package contains ROS messages and services for further homeworks and has to be present in your workspace. For debugging purposes, you can use occ_dat.zip with published occupancy map.

Detection of frontier will be done by node frontier in frontier.py. Two services should be implemented:

• Return random frontier
• Return closest frontier (Euclid distance)

Is a BFS algorith to search for frontiers.

• outer BFS - search for frontier points connected to the robot position
• inner BFS - “frontier assembly”, search for contiguous frontier points

Make sure to filter the frontiers, i.e. make sure they are reachable.

You can find pseudocode and more information in [1].

Frontier points close to the obstacles are untraversable, robot would collide when visiting them. Make sure your returned frontiers point to traversable space. Unknown map points might also contain obstacles! Robot diameter is also given in the task. Solution is to add a safety margin, inflate obstacles (and possible obstacles) in the grid. Use scipy, either approach will work results closest to the reference are obtained using binary dilation with default footprint, you only have to specify number of iterations:

https://docs.scipy.org/doc/scipy/reference/generated/scipy.ndimage.binary_dilation.html

https://docs.scipy.org/doc/scipy/reference/generated/scipy.ndimage.grey_dilation.html

Defined in: nav_msgs/OccupancyGrid

data (int[8])

• 0 == empty cell
• 1 .. 100 == (probably) occupied cell
• -1 == unknown (unseen) cell

info (nav_msgs/MapMetaData)

• resolution (float32) - “size” of cell in meters
• width - width of grid in cells
• height - height of grid in cells
• origin (geometry_msgs/Pose) - relation of origin [0,0] of the grid to the real world (e.g. map tf)

Robot position needs to be transformed to fit into the grid - translation and scaling.

Please submit the whole aro_frontier package directory in a single .zip file. aro_msgs package will be ignored. Frontier detection will be evaluated using simulation. Robot TF will be provided, make use you use correct transform (see HW03). Robot diameter param and position will be given during the testing.

[1] TOPIWALA, Anirudh; INANI, Pranav; KATHPAL, Abhishek. Frontier Based Exploration for Autonomous Robot. arXiv preprint arXiv:1806.03581, 2018.