Benchmarking Metric Ground Navigation

National Institute of Standards and Technology (NIST) has created standard testbeds for response robots, including ground, aerial, and aquatic vehicles [13]. Specialized test methods are developed to test individual robot capacity, e.g. locomotion, sensing, communication, durability. Robotarium [14] is a testbed developed to test algorithms for multi-robot research, using a fleet of miniature differential drive robots. Xiao et al [15] reviewed 20 physical testbeds for snake robots and pointed out that all of them are designed in an ad hoc manner, i.e. tailored to demonstrate the newly developed capability. They also provided suggestions on a general testbed design. The research thrust on developing robot testbeds demonstrates the robotics community’s need for standardized test methods to quantify robot performance and research progress. Similar to the aforementioned testbeds but with a different purpose, the proposed testbed is developed to benchmark mobile robot navigation systems operating in a metric world.

Thanks to the recent progress on data-driven approaches, testbeds are frequently instantiated as datasets, e.g. ImageNet [16]. In the mobile robot navigation domain, especially on the perception and estimation side, many such software testbeds have also been created [17, 18, 19, 20], where perceptual data is collected along a fixed motion trajectory. However, when arbitrary motion execution is required, such interactive testbeds become sparse. Even when motion is allowed [21, 22], the locomotion part of navigation is assumed to be trivial, i.e. the testbeds only benchmark the robot’s ability to infer “where” to navigate, instead of to generate feasible and optimal motion commands for “how” to navigate. The proposed testbed focuses on the ability to autonomously generate viable motion commands in order to navigate between two fixed points in a given environment. Since only geometric obstacles are considered, it can easily be instantiated into a physical testbed.

At each cell in the environment, the Distance to Closest Obstacle is defined as the distance from this cell to the nearest occupied space. This metric is averaged over all points in the path.

A cell’s Average Visibility is defined as the average of the distances to an obstacle along each ray in a $360^{\circ}$ scan. In our discrete space, we average the visibility along eight rays (four cardinal directions and four diagonals), then average this metric over all points in the path. Figure 2 provides examples of high and low visibility.

From a given state in the environment, a $360^{\circ}$ scan is cast up to a certain max length. The dispersion at that state is defined as the number of alternations in that scan from occupied to unoccupied space or vice versa, as shown in Figure 3.

Dispersion captures the number of potential paths out of a given location. A higher dispersion means more possible options for the navigation algorithm and therefore means the environment poses more challenges, especially for a sampling-based local planner, like DWA [2]. In our discrete space, dispersion is calculated by casting 16 rays up to a max length, and checking which are blocked or open. This metric is calculated for each point in the path and averaged over the length of the path.

The Characteristic Dimension at a given cell is defined as the visibility of the axis through the cell with the lowest visibility. In our discrete space, 8 axes (each made up of 2 rays $180^{\circ}$ apart) are cast $22.5^{\circ}$ apart from one another. Each axis’ visibility is calculated as the sum of the distances to an obstacle along both of the rays that make it up. The Characteristic Dimension is defined as the visibility of the axis with the lowest visibility. The Characteristic Dimension captures the tightness of a space. A low Distance to Closest Obstacle could occur in a relatively open space and therefore still be quite easy to navigate. Additionally, a space might be tight along one axis yet very open along another (e.g. a long tunnel) and therefore have a high Average Visibility despite being narrow. Figure 4 captures such an instance of when Distance to Closest Obstacle and Average Visibility may fail to completely represent the difficulty of a space.

Tortuosity, as a property of a curve being tortuous, is calculated over the entire path using the arc-chord ratio. The arc length is the length of the entire path, while the chord length is the length of a straight line between the start and end points. This metric captures bends in the path that make navigation more difficult compared to navigation along a relatively straight path.

We use a simulated Clearpath Jackal, a four-wheeled, differential drive, nonholonomic ground robot, in a Robot Operating System (ROS) Gazebo simulator [33] to benchmark the relative difficulty levels of the navigation environments in our dataset.

We choose two different widely used navigation planners, DWA [2] and E-Band [1] to navigate Jackal. DWA is a representative sampling-based motion planner. Given a global path produced by the A* algorithm [32], DWA generates samples of linear and angular velocities and evaluates the score of each sample based on closeness to the obstacle, to the global path, and progress toward the local goal. The action sample with the best score is executed to move the robot. The randomness in the sampling process leads to non-deterministic behavior in the same environment. E-Band is a representative optimization-based motion planner, which optimizes an initial trajectory. It deforms the trajectory using virtual bubbles along it, which are subject to repulsive force from the obstacles. The optimized trajectory acts like an elastic band. The default navigation planner from the robot manufacturer, Clearpath Robotics, is the DWA planner. We use the default planner parameters from the manufacturer¹¹1https://github.com/jackal/jackal/tree/melodic-devel/jackal_navigation/params for DWA, and the default parameters from the E-Band designer²²2http://wiki.ros.org/eband_local_planner for the E-Band planner. We set E-Band’s maximum allowable linear and angular velocities (0.5m/s and 1.57rad/s) to match with those of DWA for a fair comparison.

For each one of the 300 environments in our dataset, a pre-built map is provided to the planner, and we run five trials each for DWA and E-Band, resulting in a total number of 3000 trials (Figure 5). The final difficulty measure is the traversal time averaged over the ten trials and normalized by path length. We also compute the variance of the traversal time. A 30-second penalty is introduced to trials where the robot fails to reach the goal, e.g. getting stuck. The DWA, E-Band, and combined (averaged) with predicted navigation performance is shown in Figure 6. From left to right, the 300 environments are ordered from easy to difficult. High difficulty level is correlated with high variance. Operating with a map, DWA and E-Band achieve an average normalized traversal time of $3.30\pm 0.50$s/m and $3.24\pm 0.38$s/m, respectively. As a sampling-based planner, DWA results in higher standard deviation than the optimization-based E-Band, and is more sensitive to the increased difficulty level.

To approximate the combined effect of all five difficulty metrics, we use a simple neural network consisting of two fully connected layers with 64 neurons each. Distance to Closest Obstacle, Average Visibility, Dispersion, and Characteristic Dimension are computed for and averaged over all the states on a path. Tortuosity is computed for the entire path. All these metrics are normalized based on their mean and standard deviation (Table II). The label of the neural network output is the average traversal time normalized by path length, computed from the 3000 simulation trials. Our function approximator can achieve a 0.10 prediction loss on normalized traversal time, which corresponds to, for example, 0.50 seconds error while traversing a 5m long path.