Mini-Project 2 Authors: Charles Meehan, Nilesh Suriyarachchi, Faizan Tariq, and Achal Vyas

Research Paper Citation:

H. Umari and S. Mukhopadhyay, “Autonomous robotic exploration based on multiple rapidly-exploring randomized trees,” in 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Sep. 2017, pp. 1396–1402, doi: 10.1109/IROS.2017.8202319.

GitHub of Author Hassan Umari:

https://github.com/hasauino/rrt_exploration

ROS Wiki Link:

http://wiki.ros.org/rrt_exploration

Existing Implementation from the Research Paper

In the Umari et al. implementation, the unknown area to explore is represented as an occupancy grid which contains obstacles and free space. The occupancy grid map contains cell values of 1, 0, or -1 representing obstacles, free space, unexplored space respectively. The map exploration strategy is shown in Figure 1.

There are three main modules involved in the exploration strategy:

1. Frontier detector: It is responsible for detecting frontier points and passing them to the filter module.

2. Filter module: It clusters the frontier points and stores them. In this work, the mean shift clustering algorithm is used and deletes invalid and old frontier points. The clustering and subsequent discarding process is needed to reduce the number of frontier points because the global and local frontier detectors can provide too many frontier points which are extremely close and are redundant.

3. Task allocator module: It receives the clustered frontier points from the filter module and assigns them to a robot for exploration. While allocating it considers:

   1. 1. 1. Navigation cost: It is the expected distance to be traveled by a robot to reach a frontier point. Calculated by considering the norm of the difference between a robot’s current position and the location of a frontier point.

         2. Information cost: the area of unknown region expected to be explored for a given frontier point. The area is calculated by multiplying the number of cells within the information gain radius by the area of each cell.

         3. Revenue from a frontier point (R): For a given frontier point x_fp, and a current robot location x_r, the revenue R obtained from exploring x_fp, is calculated as:

The weight λ is used to give more importance to the information gained from exploring a frontier point, compared to the navigation cost. For each frontier point, a revenue R is calculated by using Equation 1. The point with the highest revenue is assigned to the robot for exploration.

RRT-Based Frontier Detector Module:

A. RRT-Based Frontier Detector Module:

1. 1. 1. It discovers points, here we have a point that is reached by the growing RRT tree is considered a frontier point, if this point lies in the unknown region of the map. Initial occupancy grid map starts with only unknown cells and obstacles and free space is marked as the robot explores. We make use of two versions of frontier detectors:

      2. a. Local Frontier Detector:

         1. The local detector is proposed for fast detection of frontier points in the immediate vicinity of the robot at any time.

      3. Global frontier detector:

         1. The global frontier detector is meant to detect frontier points through the whole map and in regions far from the robot. It’s similar to the local one, but line 8 is removed from the algorithm below. The tree doesn’t reset and keeps growing during the whole exploration period (i.e. until the map is completely explored) which makes the global frontier detector algorithm similar to RRT.

IMPLEMENTATION:

Their exploration strategy consists of the SLAM module, path planning module, global and local frontier detector modules, the filter module, and the robot task allocator module. Ready-made ROS packages to implement mapping and path planning were used. The implementation strategy is shown in the diagram below.

The ROS ‘gmapping’ package is used for generating the map and localizing the robot. The ‘gmapping’ package implements a SLAM algorithm that uses a Rao-Blackwellized particle filter. The ROS Navigation stack is used to control and direct the robot towards exploration goals. Path planning uses the A* algorithm which is one of the packages available inside the ROS navigation stack. The filter node subscribes to this topic, so that it can receive all detected frontier points. The filter node processes the received frontier points and then publishes remaining valid frontier points on a ROS topic which is subscribed to by the robot task allocator node. The robot task allocator node receives points provided by the filter node and assigns them for exploration.

Videos of Umari et al. Implementation

The single robot implementation was part of the paper cited at the top of this page. The multiple robot exploration was part of work continued by Umari during his thesis.

Our Group's Implementation

We implemented the map exploration method from Umari et al. for single and multiple robots on a more complex Gazebo environment. This is shown in the following two videos. The GitHub with the launch files and Gazebo world set up used for the videos can be found here, https://github.com/irishMee/CMSC818_Mini_Project2.git.

Challenges of Implementation:

• Possibly due to implementation on a VMware workstation, the runtime of the exploration for single and multiple robots was very slow. As you can see, the videos are speed up by 8x so total exploration took around 16 minutes for single robot exploration and around 24 minutes for multiple robot exploration.

• The green dots represent clustered frontier points. However, it was apparent that the decision making algorithm for picking which frontier point the robot should head to was not very efficient. There were times that the robot left an unknown area to go explore a larger unknown area, but at the cost of having to turn around and return to the original area to finish the exploration task. Therefore, this algorithm seems very biased towards information gain and not cost of total distance traveled.

  • This is something we hope to fix by using other techniques for decision making such as reinforcement learning to train the agent to make better decisions of which frontier point to explore next.