Obstacle Avoidance Benchmarking

For more information please contact: Iñaki Rañó or Javier Mínguez

  1. Introduction

    2. Nowadays, published research results in some concrete field of robotics are extremely difficult to compare with other approaches. Moreover, to asses the quality of the experimental research presented by the authors is really hard due to the unverifiable nature of their claims. The lack of experimental details and sometimes working hypothesis makes impossible to verify the author's claims about the performance of the robotic system.

    This lack of objective evaluation is spread over all robotics areas, even for well known and settled algorithms or techniques like obstacle avoidance. Several successful obstacle avoidance techniques exist in the literature (Kathib, 1986), (Borenstein and Koren, 1991), (Fox et al., 1997), (Mínguez and Montano, 2004). However, each technique can be suited for some particular situation the robot will face up, but no research has been performed on this topic. A concrete method can perform successfully in cluttered environments while others can perform better on open spaces. This is an interesting and challenging research topic with plenty of possible applications.

    At the University of Zaragoza, some members of the Robotics, Perception and Real Time Group are running a project related to the automatic evaluation of obstacle avoidance algorithms. This evaluation system will allow to classify avoidance techniques according to its performance on different environments, therefore making possible, for instance, to select one of such techniques for a specific robotic application depending on the robot workspace. This is one of the European initiatives on benchmarking funded by a Spanish research project.

  2. Automatic Evaluation Framework

    3. An obstacle avoidance technique is a mechanism that, given an obstacle configuration and a initial and goal positions, computes the best motion to drive the vehicle to the goal while avoiding collisions with the obstacles. The result is a trajectory that joins the initial and the goal. Thus, the inputs of the problem are: (i) obstacle distribution and (ii) initial and goal configurations. The output is success if a collision free trajectory that joins the initial and goal has been computed and failure otherwise. Thus, an evaluation of an obstacle avoidance mechanism should cover all the possible inputs and must be done on the basis of the quality of the output (the trajectory).

    The methodology that we propose is to build a system able to generate random obstacle, initial and goal distributions and to evaluate the output of the method (trajectory) as a function of quantitative descriptors of the inputs and the outputs. The framework has the following modules:

    On this framework the obstacle avoidance technique is just a "black-box", with a defined interface, called by the Robot Simulator module. The structure of the overall system is shown in Figure 1.


    Figure 1

  3. Automatic Evaluation Software

    4. A software system for the automatic evaluation is currently under development. A deep analysis of the requirements has been performed in order to build a modular, extensible an efficient software package. We choose to build out system using the C++ language since it provides all the desired features:

    1. Modularity: C++ allows Object Oriented design and programming.
    2. Extensibility: As an ongoing research project the framework must be highly extensible.
    3. Efficient: The automatic evaluation protocol needs a statistically significant number of tests, therefore an efficient programming language was required.

    The choice of this programming language allows to have a multiplatform system, since compilers and useful libraries are available for different OS. As the whole project is expected to be Open Source we decided to base the framework on open source libraries.

    Following the automatic evaluation framework decomposition we identified three main software modules to be developed. (i) The scenario generator, (ii) The trajectory generator and finally (iii) The evaluation and table builder module.


    (i) The scenario generator: This module can generate scenarios with random circular obstacles, compute the scenario features (density, clearness, etc) and build histograms of the scenarios based on selected features. A Graphical User Interface has been also designed. It allows to manage scenario lists, copy and paste scenarios and store or retrieve from hard disks. Figure 2 shows a screenshot of the scenario generation GUI.

    Figure 2

    (ii) The trajectory generation and characterisation module loads the obstacle avoidance technique as a dynamic library and launches tests with random initial and goal positions on the scenarios previously generated. This module also computes some defined descriptors of the generated trajectory like; success, optimality or safety of the path. For this module no Graphical User Interface is built since the amount of tests to perform is huge and no real time simulations are desired. Figure 3 shows the trajectory generated using a potential method on a concrete scenario from the initial (qinit) position to the target point (qgoal). In Figure 3(a) the optimal trajectory is also depicted, while Figure 3(b) shows represents the minimal distance to obstacles on the scenario. The trajectory characterisation computes trajectory descriptors based on the optimal (minimum length) path and safest (maximum distance to obstacles) path.

    Figure 3(a)
    Figure 3(b)

    (iii) The evaluation and table builder module takes as input the output of the other two modules and produces as output a table with the ratios of trajectories falling on the appropriate descriptor ranges as presented in Table 1. This table presents the safety measure of the trajectory generated by the obstacle avoidance algorithm proposed in (Mínguez and Montano, 2004) for different scenario densities. As can be seen for low density scenarios (in the range 0-0.2) all the trajectories are quite safe (fall in the range 0.8-1). However, for dense scenarios the algorithm does produce some non optimal safe trajectories.

    S\D [0,0.2) [0.2,0.4) [0.4,0.6) [0.6,0.8) [0.8,1)
    [0,0.2) 0 0.0 0.0 0.4 0.50
    [0.2,0.4) 0 0.0 0.0 0.0 0.0
    [0.4,0.6) 0 0.2 0.4 0.2 0.0
    [0.6,0.8) 0 0.2 0.2 0.2 0.33
    [0.8,1) 1 0.6 0.4 0.2 0.17
    Table 1: Results for Density (D) vs. Safety (S)

    We plan to build tables representing the different scenario and trajectory descriptors for the obstacle avoidance techniques available in the literature.

  4. Related Publications

  5. Bibliography