{{indexmenu_n>5}}

===== t1e-frontiers - Determination of Frontiers for Robotic Exploration ======

In mobile-robot exploration, the robot has to select its next navigational goals autonomously. In exploration, the goal selection show follows information-rich regions of interest.
The existing solution is to use the so-called free edges (border between the free and unknown parts of the map) that are called frontiers.
The main task is to implement a function to find the free-edge cells and cluster them to obtain a list of free-edge **representatives** from which the next navigational goals for exploration can be selected.

|**Files**  |  ''Frontiers.py'' - File to be implemented \\ ''utils.py'' - Helpers for evaluation, drawing, and saving figures \\ ''data'' - Scenarios and reference solutions in pkl files \\ ''t1e-frontiers.py'' - Evaluation script |
|**Resources**  |  {{ :courses:crl-courses:redcp:tasks:redcp.zip | redcp.zip}}, \\ {{ :courses:crl-courses:redcp:tasks:t1e-frontiers.zip |}} - **<fc #ff0000>Initial files and evaluation script</fc>** |

<note tip>Implement and revise
  * ''Frontiers.find_free_edge_frontiers_representatives()'' in ''Frontiers.py'',
  * ''Mapper.update_free()'' in ''Mapper.py'',
  * ''Map.update_occupied()'' in ''Mapper.py''.
  * You can use ''ControllerReactive'' from [[:courses:crl-courses:redcp:tasks:t2-react|]] or the provided ''ControllerReactive.py''.
</note>

----

===Assignment===
In ''Frontiers.py'', implement the ''find_free_edge_frontiers_representatives()'' function to find the representatives of free-edge frontiers that are centroids of the cells at the border between the free and unknown cells.
A free-edge cell is a free cell that neighborhoods with at least one unknown cell.
Free-edges are sets of free-edge cells connected into the connected component (8-neighborhood, a.k.a. 2 jumps connected component, is considered).
The **considered representatives of the free-edge frontiers** are centroids of the segmented free edges.

The input parameter of the function is: 
  - ''grid_map'' - [[:courses:crl-courses:redcp:tasks:data_types|OccupancyGrid]] - grid map (possibly after obstacle growing to ensure the robot can reach the frontiers; however, it still needs to have //unknown cells//.

The function returns:
  - the [[:courses:crl-courses:redcp:tasks:data_types|Pose[]]] - list of representatives of the free-edge frontiers;
  - ''None'' - if there are no representatives determined.

The ''find_free_edge_frontiers_representatives()'' function in the ''Frontiers.py'' class has the following prescription.
<code python>
    def find_free_edge_frontiers_representatives(self, grid_map):
        """Method to find the representatives of free-edge frontiers (edge clusters between the free and unknown areas)
        Args:
            grid_map: OccupancyGrid - grid map of the environment
        Returns:
            pose_list: Pose[] - list of the representatives of the free edges
        """
</code>

----

=== Approach ===
There are several ways how to accomplish the determination of the frontier-based navigational goals for the exploration. 
  The recommended approach for detecting representatives of the free-edge frontiers consists of the following three steps.
  - Detection of free-edge cells;
  - Connecting free edges into the connected components;
  - Calculation of the free-edge centroids.
The individual steps are detailed in the rest of the presented description.
----

==== Free-edge cells detection ====
First, the detection of the free-edge cells is performed.
The free-edge cell $m_i$ is a free cell that is incident with an unknown cell.
Even though we can initialize the occupancy grid with 0.5 for the unknown state of the cell, we can further threshold occupancy probability to be free for the threshold less or equal $CELL\_FREE = 0.4$ and occupied for the threshold above or equal $CELL\_OCC = 0.6$.
Thus, a cell is a free-edge cell if the following holds.
  * A free-edge cell is a free cell, i.e., $P(m_i = occupied \vert z) <= CELL\_FREE$.
  * A free-edge cell borders at least one unknown cell, $\exists m_j \in 8\mathrm{-neighborhood\,\,of\,\,} m_i \vert CELL\_FREE < P(m_j = occupied \vert z) < CELL\_OCC$.
An efficient approach to free-cell detection is using the 2D convolution with subsequent thresholding. 
The task is to find a 2D convolution mask to distinguish between the different constitutions of cell 8-neighborhood consisting of free, unknown, and occupied cells.++ Hint | 
You should draw the bounding examples of 8-neighborhood and consider the 2D convolution as a weighted sum of the neighborhood.  
++

The 2D convolution itself can be done using the ''scipy.ndimage'' library using the following code: 
<code python>
import scipy.ndimage as ndimg
data_c = ndimg.convolve(data, mask, mode='constant', cval=0.0)
</code>
Generally, the expected output is a grid with ''1'' wherever the free-edge cell is and ''0'' elsewhere. 
An example of the convolution result and subsequent thresholding to obtain the free cells is visualized in the following figure. 
++++ Figure (click to view) |
From left to right:
  * original gridmap,
  * gridmap after convolution,
  * thresholded positions of the free cells.

| {{:courses:crl-courses:redcp:tasks:gridmap.png?500|}} | {{:courses:crl-courses:redcp:tasks:gridmap_convolution.png?700|}} | {{:courses:crl-courses:redcp:tasks:gridmap_freedges.png?700|}} |
++++

== Free-edge clustering ==
The second step is to perform the connected component analysis on the free-edge cells. 
For inspiration, you can see an explanatory overview [[https://datacarpentry.org/image-processing/09-connected-components/|connected component analysis]].
The main idea is to connect the free-edge cells that coincide with the connected component to effectively reduce the number of frontiers and select only the representatives of the whole cluster. 

For the connectivity analysis, you can use the following code:
<code python>
import skimage.measure as skm
labeled_image, num_labels = skm.label(free_cells, connectivity=2, return_num=True)
</code>
An example of the connected free-edge clusters is visualized in the following figure, with free-edge centroids marked by red points.

{{:courses:crl-courses:redcp:tasks:gridmap_freedges_centroids.png?800|}}

== Free-edge centroids ==
Finally, obtaining the cluster centroids as the mean of $x, y$ coordinates of connected free-edge is necessary. 

----

=== Example behavior ===
| {{:courses:crl-courses:redcp:tasks:map1.png?300|}} | {{:courses:crl-courses:redcp:tasks:map2.png?300|}} | {{:courses:crl-courses:redcp:tasks:map3.png?300|}} |


----

=== Evaluation ===
The code can be evaluated using the script ''t1e-frontiers.py'').
<code python>
    frontiers = Frontiers()
    dataset = pickle.load( open( "data/frontier_detection_eval.pkl", "rb" ) )
    reference_frontiers = pickle.load( open( "data/frontier_reference.pkl", "rb" ) )

    for idx, gridmap in enumerate(dataset):
        print("Process scenario %2d" % idx)
        goal_locations_ref = reference_frontiers[idx] #load the reference result
        if goal_locations_ref is None:
            print("WARN: Reference goal locations None!")
            break 
        
        goal_locations = frontiers.find_free_edge_frontiers_representatives(gridmap) #find free edges
        if goal_locations is None:
            print("WARN: Goal locations None!")
            break 
        # compare goal_locations with goal_locations_ref
</code>