Metrics for the Evaluation of DisCSP: Some Experiments on Multi-robot Exploration

Abstract

Many algorithms to solve Distributed Constraint Satisfaction Problems (DisCSP) have been introduced in the literature. In this paper, we propose to compare three different algorithms to solve DisCSP. Contrary to algorithms of the literature which are evaluated on graph coloring problems or uniform random binary DisCSPs, we use a multi-robot exploration problem. We show that, for this real world application, the comparison of algorithms may be improved by using additional metrics than those used in the literature. We will define other metrics that can be used for measuring different aspects of the multi-robot exploration problem. The aim of our attempt for defining metrics is to analyze and compare different aspects of complexity of this multi-robot problem. We will observe that using both classical and real world metrics is interesting to obtain a better and more precise comparison.