Your goal in this task will be to implement detection of frontiers in an occupancy grid. See template in aro_frontier in hw7.zip 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.

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.

For running the code, use provided frontier.launch file. To obtain published OccupancyGrid on the /occupancy topic, you can execute rosbag play -l occ_dat.bag from the aro_planning/config directory obtained for HW05. To provide robot position transform, you can execute:

rosrun tf2_ros static_transform_publisher x y z r p y map base_footprint

The tested services can be called using the command line:

rosservice call /get_closest_frontier

rosservice call /get_random_frontier

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 HW04). 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.