{{indexmenu_n>6}}
===== t1f-exploration - Robotic information gathering - Mobile robot exploration  ======

|**Files**  |  ''Explorer.py'' - File to be implemented \\ ''utils.py'' - Helpers for evaluation, drawing, and saving figures \\ ''data'' - Scenarios and reference solutions in bag files \\ ''t1f-exploration.py'' - Evaluation script |
|**Resources**  | [[courses:crl-courses:redcp:tutorials:simloc|Introduction to CoppeliaSim/V-REP and Open-Loop Robot Locomotion Control]] \\ [[courses:crl-courses:redcp:tutorials:reactive|Exteroceptive sensing and Reactive-based Obstacle Avoidance]] \\ {{ :courses:crl-courses:redcp:tasks:redcp.zip | redcp.zip}}, \\ {{ :courses:crl-courses:redcp:tasks:t1f-exploration.zip |}} - **<fc #ff0000>Initial files and evaluation script</fc>** |

<note tip>Implement and revise
  * ''Explorer.mapping()'' in ''Explorer.py'',
  * ''Explorer.planning()'' in ''Explorer.py'',
  * ''Explorer.path_following()'' in ''Explorer.py''.
  * You can use the provided ''Explorer.py'' and modify or derive a new class with the improved ''planning()''.
  * You can use ''ControllerReactive'' from [[:courses:crl-courses:redcp:tasks:t1b-react|]] or the provided ''ControllerReactive.py''.
  * You can use ''Planner'' from [[:courses:crl-courses:redcp:tasks:t1c-plan|]] or the provided ''Planner.py''.
  * You can use ''Mapper'' from [[:courses:crl-courses:redcp:tasks:t1d-map|]] or the provided ''Mapper.py''.
  * You can use ''Frontiers'' from [[:courses:crl-courses:redcp:tasks:t1e-frontiers|]] or the provided ''Frontiers.py''.
</note>


----

===Assignment===
Autonomous mobile robotic exploration is a complex problem with relatively challenging implementation using a multi-thread environment. 
For the frontier-based exploration, the particular building blocks for path planning, mapping, and frontiers extractions have been developed in the corresponding tasks  [[:courses:crl-courses:redcp:tasks:t1c-plan|]], [[:courses:crl-courses:redcp:tasks:t1d-map|]], and [[:courses:crl-courses:redcp:tasks:t1e-frontiers|]], respectively.
Besides, the plan to navigate the robot towards the not yet explored part of the environment can be executed by the reactive path follower implemented in  [[:courses:crl-courses:redcp:tasks:t1b-react|]].

The provided sources in {{ :courses:crl-courses:redcp:tasks:t1f-exploration.zip |}} include an example implementation of the multi-thread applications, albeit it can be eventually adjusted as needed. 

The main task is to implement the decision-making strategy, that is, to determine the next navigation goal (plan) in the function ''planning()'' of the ''Explorer'' class.
Therefore, the whole application logic is encapsulated in the ''ExplorerBase'' class to make the problem approachable. 
There are three main threads of ''Explorer'' with an additional thread for visualization (in ''ExplorerBase'') and one more thread of the ''HexapodRobot''. 
These threads run at a different rate as it is unnecessary to run planning and visualization at high frequency.

Due to a multi-thread setup, it is desirable to utilize exclusive access to the shared data structures realized by the shared variables of the base class ''ExplorerBase'', which is sufficient for the implementation of the task.

<note tip>Any of the provided source files can be adjusted and modified as needed!</note>

==== Approach ====
Three functions need to be implemented for the working autonomous exploration.
The first is ''mapping()'', a direct utilization of the of [[:courses:crl-courses:redcp:tasks:t1d-map|]] with laser scan fusion into a grid map. Since it is shared with the planning thread and visualization, the access is protected by the ''mutex_gridmap''.
The second is ''planning()'' that consists of the following steps 
  - Determination of the frontiers and representatives of the free edges from the [[:courses:crl-courses:redcp:tasks:t1e-frontiers|]].
  - Selection of the most suitable navigation goal to ensure its reachability, such as using map grow from [[:courses:crl-courses:redcp:tasks:t1c-plan|]].
  - Planning a path with the eventual simplification that can be directly based on the solution of [[:courses:crl-courses:redcp:tasks:t1c-plan|]].
  - Passing the sequence of waypoints to the path-following thread.
The path following thread is a variant of the reactive obstacle avoidance [[:courses:crl-courses:redcp:tasks:t1b-react|]], where we need to address handling plans provided by the planning thread. Thus, we need to set a new goal location when a new plan is prepared.

The provided sources represent a basic implementation of the exploration, which is working but is neither very reliable nor robust.
The limitations and possible improvements are as follows.
----
 
=== Limitations and Possible Solutions ===
The provided default implementation has several issues and drawbacks that can result in less robust and reliable autonomous exploration missions. 
The main issues with the possible solutions are the following.
  * The frontiers are determined directly from the mapped occupancy grid. Even though using free edges representative improves the chances of the navigation goal at a sufficient distance from the obstacles, it is not explicitly guaranteed that the goals are reachable.
     * We can ensure the frontiers are reachable by adjusting the occupancy grid by obstacles growing and then applying frontiers detection.
     * Alternatively, we can detect the frontiers and filter out those not reachable by a feasible path in a map for grown obstacles.
     * Notice that once obstacles are grown in the map with only an initial laser scan, the robot might be surrounded by the grown obstacles. Therefore, it is necessary to mark the space occupied by the robot as free space since the robot can be in such a place.
  * Selection of the next navigation goal is based on its Euclidean distance to the current robot position.
     * We can employ a length of the path to the goal locations to have a more realistic estimate of the related travel cost.
     * The utilized hexapod walking robot is relatively slow in turn motion; therefore, locations close to the Euclidean distance might need to turn the robot, which is slow. Thus considering orientation in the travel cost can improve the performance.++ Hint |
We can also achieve the expected behavior by filtering out too-close locations.
++
  * The robot might be navigated towards the goal in the way the laser scan is not covering the area because of too abtuse angle. 
    * Using representatives of the free edges partially addressed that as a side effect. However, we can employ the sensor model with the explicit request on how the not yet explored area is approached and covered.
  * The initial implementation uses a static grid with a fixed size. 
    * The grid can be adjusted as new areas are explored during the exploration.

==== Possible Further Extensions ====

A more demanding possible further extensions are as follows.
  * In addition to a greedy selection of the next navigation goal, we can consider a longer planning horizon and utilize the so-called TSP distance cost. The idea is to plan a path to visit all the current representatives of the free edges as a (heuristic) solution of the open tour variant of the TSP. Such a solution is more stable with re-planning steps, which can further support a faster re-planning loop.
  * The determination and selection of the next navigational goal can be based on the utility of information measures, such as mutual information gain.