Action Selection in Cooperative Robot Soccer using Case-Based Reasoning

Designing the decision-making engine of a team of robots is a challenging task, not only due to the complexity of the environment where the robots usually perform their task, which include uncertainty, dynamism and imprecision, but also because the coordination of the team must be included in this design. The robots must be aware of other robots’ actions to cooperate and to successfully achieve their common goal. Besides, decisions must be made in real-time and with limited computational resources. This thesis contributes a novel case-based approach for action selection and coordination in joint multi-robot tasks in real environments. This approach has been applied and evaluated in the representative domain of robot soccer, although the ideas presented are applicable to domains such as disaster rescue operations, exploration of unknown environments and underwater surveillance, among others. The retrieval process proposes a case to reuse, evaluating the candidate cases through different measures to overcome the real world characteristics, including the adversarial component which is a key ingredient in the robot soccer domain. Unlike classical case-based reasoning engines, the case reuse consists in the execution of a set of actions through a team of robots. Therefore, from the multi-robot perspective, the system has to include a mechanism for deciding who does what and how. In this thesis, we propose a multi-robot architecture along with a coordination mechanism to address these issues. We have validated the approach experimentally both in a simulated environment and with real robots. The results showed that our approach achieves the expected goals of the thesis, i.e. designing the behavior of a cooperative team of robots. Moreover, the experimentation also showed the advantages of using collaborative strategies in contrast to individualistic ones, where the adversarial component plays an important role.

1 Introduction, 1
1.1 Motivation and Overview, 3
1.2 Problem Domain, 7
1.3 Contributions, 10
1.4 Publications, 11
1.5 Outline of the Thesis, 11
2 CBR Preliminaries and Related Work, 13
2.1 Case Based Reasoning, 13
2.2 CBR Applied to RoboCup, 16
2.2.1 Karol et al, 16
2.2.2 Lin, Chen and Liu, 16
2.2.3 Berger and L ¨ammel, 17
2.2.4 Wendler et. al, 17
2.2.5 Marling et al, 18
2.2.6 Ahmadi et al, 19
2.2.7 Steffens, 19
2.3 Other Models Applied to RoboCup, 20

2.3.1 Learning from Observation or Imitation, 20
2.3.2 Reinforcement Learning, 20
2.3.3 Pattern Recognition, 22
2.3.4 Fuzzy Theory, 22
2.3.5 Planning, 23
2.3.6 Neural Networks, 24
2.3.7 Evolutionary Algorithms, 25
2.3.8 Other Approaches, 26
2.4 CBR Applied to Other Robotic-Related Domains, 27
2.5 Summary, 29
3 The Retrieval Step, 33
3.1 Case Definition, 33
3.1.1 Problem Description, 33
3.1.2 Solution Description, 35
3.1.3 Case Scope Representation, 37
3.1.4 Case Example, 38
3.2 Case Base Description,39

3.3 Case Retrieval, 41
3.3.1 Similarity Measure, 41
3.3.2 Cost Measure, 44
3.3.3 Case Applicability Measure, 47
3.3.4 Case Filtering, 50
3.3.5 Experiments, 53
3.4 Conclusions and Future Work, 59
4 Case Reuse through a Multi-Robot System, 61
4.1 Robot Architecture, 61
4.1.1 Deliberative System, 63
4.1.2 Executive System, 64
4.2 Multi-Robot System and Case Reuse, 65
4.3 Conclusions and Future Work, 69
5 Learning the Scopes of Cases, 71
5.1 Scope Adaptation Algorithm, 72
5.1.1 When to Adjust the Values, 73
5.1.2 How to Adjust the Values, 74
5.1.3 Example, 76
5.2 Acquiring New Cases, 78
5.3 Experiments, 78
5.3.1 Simulation Experiments, 78
5.3.2 Real World Experiments, 83
5.4 Conclusions and Future Work, 88
6 Experimentation, 89
6.1 CBR System Settings, 90
6.2 Experiments Setup, 95
6.2.1 Robot’s Behaviors, 95
6.2.2 The Scenarios, 96
6.2.3 Evaluation Measures, 98
6.3 Simulation Experiments, 98
6.3.1 The Simulator, 98
6.3.2 Simulation Results, 99
6.4 Real Robot Experiments, 104
6.4.1 The Robots, 104
6.4.2 Results, 106
6.5 A Trial Example, 112
6.6 Discussion and Future Work , 124
7 Conclusions and Future Work, 127
7.1 Summary of the Contributions, 127
7.2 Future Directions, 129
Bibliography, 133