Abstract
This paper proposes a new Case-Based Reasoning (CBR) approach, named Q-CBR, that uses Qualitative Spatial Reasoning theory to model, retrieve and reuse cases by means of spatial relations. Qualitative relations between objects, represented in terms of the
Introduction
Case-Based Reasoning (CBR) is a paradigm of Artificial Intelligence (AI) that uses the knowledge obtained in past situations, defined in terms of cases, to solve new problems. It combines processes for solving a problem and learning from this experience in a process cycle known as the four REs: retrieve, reuse, revise and retain [1]. The retrieval step searches the case base for the most similar cases to a given problem, retrieving the candidate cases; the reuse step selects the most similar case to be used as a solution to the problem; the revise step analyses the proposed solution and the retain step decides if the reused case is useful to solve the new problem.
In general, when CBR is applied in problems where the objects’ positions in space is relevant, a metric coordinate system is used to represent case similarity. Consequently, there is a large number of distinct similarity measurement strategies based on numerical distances or other metric information [6].
In some domains, however, a metric representation is not the most effective. For instance, in a humanoid-robot domain, where a video camera is the main source of information, the use of a metric coordinate system to represent an object’s position generates a high error rate. In this context, qualitative relations between spatial entities can provide a more appropriate representation of the robot’s environment. From the distance and direction information obtained by the robot’s sensors, qualitative spatial regions can be defined, allowing for reasoning about, and comparison of, relations between domain objects, the regions in which the objects are located and their occupancy regions.
This paper proposes a novel CBR approach using Qualitative Spatial Reasoning (QSR) to model cases and to serve as the basis for retrieval and reuse algorithms. The idea is to use
Ros et al. [35] applies CBR for the coordinated action selection in the robot-soccer domain, using the Cartesian coordinate system to represent the position of objects in the field. The present work differs from Ros et al. since it discretizes the world following a qualitative spatial reasoning formalism and proposes a faster retrieval algorithm that can be used in robots with limited processing power. Finally, by running the algorithms proposed in this paper, the robots performed a higher average number of goals than running a metrical-based CBR.
In the remainder of this work we present the CBR and QSR representations, which are the foundations of this work (Section 2), the proposed Qualitative Case-Based Reasoning method (Section 3), the results obtained during the retrieval and reuse steps (Section 4) and the related work (Section 5).
Research background
This section presents the two methodologies that are used in this work, Case-Based Reasoning (CBR) and Qualitative Spatial Reasoning (QSR).
Case-Based Reasoning
Case-Based Reasoning (CBR) [1] can be summarized by means of two principles: the existence of real-world regularities (i.e., similar problems have similar solutions) and the tendency to encounter similar problems [17].
Given a new problem, CBR uses the knowledge of previous situations (cases) to find a similar case that can be reused to solve the new problem.
A case in the robot-soccer domain can be defined as the following triple [35]:
According to [35], the problem description (P) corresponds to the situation in which the case can be used, representing the global coordinates of the objects in the case. For instance, in the robot-soccer domain, the problem description of a case can include the position of any object in the soccer field. Considering a case with v teammates and u opponents, P can be defined as:
The solution description (A) is composed of a sequence of actions that each agent (that is part of the solution) must perform to solve the problem. Let v be the number of agents that are part of the solution and p, the number of actions that each agent can perform. A can be defined by means of one set of actions
The case-scope representation (K) is defined as elliptic regions around the object’s positions, with radii
In the robot-soccer domain, the case definition considers that the robots have complete knowledge about the position of each object in the field, so, they are able to recognize each robot identifier and its coordinate in the field. As the case solution is composed of a sequence of actions, some times an action can be represented as no action. When this occurs, the robot waits until the next action is received.
Ros et al. [35] also proposed a retrieval method where cases are evaluated along three important aspects: the similarity between problem and case; the cost of adapting a problem to a case; and, the applicability of a solution to a case. The similarity function was defined measuring the distance between robots and the ball in a problem and in a case, the adaptation cost measures the distance the robots have to move from their current positions to their adapted positions and the applicability measure takes into account the adversarial component of the domain, i.e., one solution retrieved in the case depends on the opponents’ positions.
In addition to the work of Ros et al. [35], other works have used CBR in the robot-soccer domain. Lin, Liu and Chen [19] presented one of the first architectures that includes a deliberative CBR system for soccer-playing agents; Karol et al. [16] proposed high-level planning strategies, which included a CBR system. In Marling et al. [21], three case-based reasoning prototypes were developed for a team in the RoboCup small-size league, where CBR was used to position the goalie, select team formations and recognize game states for the team.
Floyd, Esfandiari and Lam [12] used CBR in the RoboCup Soccer Simulation League, where the agents perceive the objects in the field, convert this perception into a case structure and retrieve the k-most similar cases, using k-nearest-neighbor search. This work proposed two similarity functions and allows an agent to imitate the actions of a player.
The work presented in Davoust, Floyd and Esfandiari [5] proposed the use of fuzzy histograms to represent the objects in the field and a similarity metric, based on the Jacard Coefficient, that matches scenes in a given problem to cases in a case base, retrieving the action related to the most similar case. Altaf et al. [2] proposed an architecture to control more complex soccer behaviors such as dribbling and goal scoring applied to humanoid multi-robot scenarios.
The main difference between the work cited in this section and the present proposal is the use of a qualitative formalism to model, retrieve and reuse cases. Also, the work described in this paper was tested in a real-robot domain, considering robot failures and noises, whereas in much previous works, experiments were conducted in simulated environments, under optimal conditions, with a global knowledge of the environment or using numerical values. More specifically, in our proposal the agents have local vision and use qualitative spatial representations to retrieve and reuse cases. Even if the qualitative position of an object is different from the precise object location, the retrieval algorithm proposed in this paper retrieves the case with the lowest adaptation cost.
The next section introduces the field of qualitative spatial reasoning in AI, describes the
Qualitative Spatial Reasoning
Qualitative Spatial Reasoning (QSR) is a subfield of knowledge representation in AI that formalizes qualitative spatial relations between objects, aiming at modeling the human common sense understanding of the world [39]. QSR has been applied in distinct fields, such as robot navigation and self-localization, geographic information systems and computer vision [3]. Formalisms in QSR verse on various spatial modalities, such as mereotopology [31], qualitative directions [13,33], occlusion [22,30,36] and so forth [3,18].
Among the several proposed formalisms in the QSR literature, the Oriented Point Relation Algebra (
In
In order to represent distances, Moratz and Wallgrün [24] proposed a definition of relative distance based on local references called elevations. Elevations are defined by the height of objects, whose projection in the 2D plane defines a circle around the object’s locations, that is used as a distance reference. The size of this projection is represented by δ, and all distance ratios are calculated taking into consideration n and δ, where n is the distance granularity [8]. The granularity also applies to elevations in order to provide an appropriate level of abstraction for distance relations. Equation (5) calculates the boundaries of qualitative distances around an elevated point A, where
In this context, the distance relations between two points A and B are represented as
The idea of elevated points can be combined with a directional calculus, enhancing its expressiveness. An example is
The
For notational simplicity, the distance and orientation granularity are treated as having the same value (

For each jointly exhaustive and pairwise disjoint set of QSR relations there is a specific Conceptual Neighborhood Diagram (CND) [14]. A CND is a graph with nodes corresponding to a relation between spatial entities and edges corresponding to a pair of conceptual neighbors (i.e. there is no other relation from the set that represents the transition from one relation to the other in the pair). Randell and Witkowski [32] have used CND and similarity matrix as a tool to compare and measure the distance between sets of spatial regions. The work of Weghe and Maeyer [7] used a QSR formalism and its CND to represent and reason about movements of objects, measuring the distance between the relations of two objects. In this paper, we apply a Conceptual Neighborhood Diagram as a tool to measure the distance between a new problem and items in a case base in order to retrieve the most similar case to the problem. This idea is developed in the next section.
This section presents the Qualitative Case-Based Reasoning (Q-CBR) method, the qualitative spatial modeling for the cases, the CND of
Qualitative direction and distance
This work uses
Considering an environment of length 9.00 meters and width 6.00 meters (a robot-soccer field), a granularity parameter of

Qualitative orientation representation.

Qualitative distance representation.
In this work we consider a granularity parameter of

Qualitative relations for distance and orientation.

CND of the proposed
The notion of similarly and CND in the work of Randell and Witkowski [32] can be used to define a distance function
The distance matrix for
Inspired by the work of Ros et al. [35], we define a case (C) as the problem description (P) and the solution description (A), represented by:
The problem description (P) corresponds to the qualitative spatial relations between an agent and the objects in the environment, given by the qualitative direction and distance to each object, from the agent’s viewpoint. P is given by:
The solution description (A) is that defined in Section 2 above.
In contrast to the work presented in [35] (described in Section 2), the use of the case scope (K) is not necessary in the qualitative case representation proposed here, since in the present paper objects are located in qualitative regions. In this work K is only necessary in the experiments (Section 4), where the results obtained with our method is compared to those of Ros et al. [35].
Qualitative case retrieval
The present work uses the distance between relations in the CND to compute the similarity between the new problem and the cases in the case base. This can be done by means of a distance function based on the matrix described in Section 3.1. This qualitative distance function can be defined as:
The distance function is used to calculate case similarity by means of the qualitative similarity function defined by:
A retrieved case is not always directly applicable to the problem at hand without some adaptation. If this is the case, the qualitative adaptation cost function (shown in Equation (10)) is applied.
Algorithm 1 represents the proposed retrieval method based on the CND distance measure and adaptation cost. This algorithm has two lists:

Retrieval step using CND similarity measure
Figure 6 shows an example of a qualitative retrieval task with three stored cases. In this example, one agent is the reference (positioned as EQ) and two other objects are randomly positioned in the environment. Consider one teammate robot (
Figure 6 (top-left) shows the CND of the new problem, representing a snapshot of the objects’ position in the environment, where the ball is placed very close and in front of the robot
After running the retrieval algorithm the result is: (a) case #1 (top-right) with

Example of stored cases and case retrieval.
The reuse step consists of adapting the position of the robots in the problem to the qualitative position of the retrieved case. Basically, this step contains three agents: the coordinator robot (
Algorithm 2 presents the proposed reuse method, that focuses on calculating how the

Reuse step using Composition Algorithm
Before sharing the retrieved case with the agents, an intermediate step is necessary: the adaptation step. It consists of the inference of the coordinator’s qualitative orientation and distance with respect to the point of view of the executor robot. The adaptation step is performed by the Composition Algorithm (CA) as presented in Algorithm 3, proposed by Perico et al. [27], which infers the qualitative orientation and distance from
Algorithm 3 receives the problem, the case, the coordinator robot ID and the executor robot ID. Line 2 calculates all the relations between the coordinator robot (
Finally, line 5 calculates the rough distance between

Composition Algorithm
Function

Lines 5 and 14 (Algorithm 4) compute the composition of
According to [25],
Equation (13) verifies a complete turn and Equation (14) returns the sign of an angle, as:
Using triangulation, Algorithm 5 reduces the number of possible relations in the disjunction, resulting in a qualitative direction.

Triangulation – Restricting the set of
In order to exemplify the reuse step using CA, Fig. 7 presents the coordinator robot’s (
The direction and distance labels were hidden to allow clear visualization.

Example of Reuse step using Composition Algorithm: changing frame of reference.
This section presents the experiments and results obtained applying the algorithms introduced in this work to the humanoid-robot soccer environment. Two types of experiments are performed: (1) in a simulator: where we compared our qualitative case-based algorithms with the metric approach proposed by Ros et al. [35] and with a reactive agent; (2) in a real humanoid-robot domain: where our qualitative case-based algorithms were compared with a reactive agent.
The experiments in this section aim at analyzing which of the approaches resulted in more goals scored and fewer errors, and to compare the retrieval time of cases between metric and qualitative methods. The following sections present the software architecture used in the experiments, describe the two experiments performed as well as the results obtained.
RoboFEI Humanoid Soccer Simulator
Both simulation and real robot experiments were conducted using software developed with the purpose of enabling the reproduction of experiments and performance comparison of different algorithms: the RoboFEI Humanoid Soccer Simulator. This software uses the Cross architecture described in Perico et al. [29], which is based on low-level tasks, such as vision, control and communication processes, allowing users to develop and test high-level decision-making algorithms in simulation and transfer them to real robots without the need of much software modifications.
The Cross architecture (Fig. 8) is a hybrid architecture, because there are some aspects of reactive and hierarchical paradigms. The processes are completely independent from one another, and they can be grouped into vision, localization, decision-making, planning, communication, perception and control systems, each of which communicate to each other using a shared memory. A major process, named management process, is responsible to launch, synchronize and monitor all the other processes.

RoboFEI Humanoid Soccer Simulator software architecture.
The RoboFEI Humanoid Soccer Simulator [28] is an open-source simulator, written in Python, but it allows the integration with other programming languages like C and
In this work, experiments were performed using an Intel NUC i5 with 8 GB SDRAM running Ubuntu 14.04 LTS. For reproducibility reasons, the simulator, along with the source code used in the experiments reported below, are available at the URL
In order to perform the experiments in the simulator, two scenarios were created, as shown in Fig. 9. In the first scenario (Fig. 9(a)) a ball and a robot (B1) are positioned in the center of the field and the teammate (B2) is positioned on the left and in the middle of the field. There are also a goalkeeper (B3) and three opponents (B4, B5 and B6) positioned as defenders. In the second scenario (Fig. 9(b)) the ball, B1 and B2 are positioned in the attacking field and four opponent robots are positioned as in scenario #1.

Two scenarios created for simulated experiments.
Results of simulation experiments (mean and standard deviation for 40 trials of 10 minutes)
A centralized case base was used in both scenarios, in which the robot that is the closest to the ball assumes the position of coordinator, being responsible for the retrieval process (in both, the qualitative and the metric approaches) and for the coordination of collective actions in the reuse process. The coordinator robot transmits wirelessly the adapted positions and actions that the other robots must perform, which are received and executed by the executor agents.
Two case bases were created and populated: (1) a metric case base: with 20 real cases (robots positioned on the offensive-half of the field) and 180 random cases (robots randomly positioned on all the field) and three actions for each robot, and (2) a qualitative case base: with the same 200 cases represented as qualitative relations. The 20 real cases represent specific positions of the robots and the actions that each robot must perform to solve a problem, such as a soccer set play. In the reactive approach, only reactive actions were implemented, in which the robot looks for the ball, walks toward it, aligns itself with respect to the ball and kicks it, without any team coordination.
Although the world discretization presented in Section 3.1 defines 8 qualitative regions of direction, during the experiments only 7 qualitative regions were used due to the RoboCup rules that limits camera panning movement to
For comparison purposes, 40 trials of 10 minutes were performed for each scenario and for each algorithm tested. In each trial, the number of goals scored was considered, as well as the number of near misses and the number of errors. A near miss happens when the ball is kicked and goes out of the field, but passing near one of the goalposts. An error is a situation where a robot cannot find the ball or when the sequence of coordinated actions do not result in a goal or in a near miss.
Table 1 shows the results obtained for each of the algorithms tested. Q-CBR had a higher average number of goals when compared to the metric algorithm. Both Q-CBR and the metric algorithm outperform the reactive agent in the scenarios considered, executing an average of 32.28 (Q-CBR) and 31.11 (CBR) retrievals per trial. Student’s t-test [26] was applied in each scenario and the results indicate that Q-CBR is statistically better, with a certainty of at least 90%.
Another advantage of using Q-CBR is in the case-retrieval time. The results presented in Table 2 show that Q-CBR is about 3 times faster than the metric algorithm. The improvement in the retrieval time is due to the strategy of the qualitative similarity measurement, as shown in Algorithm 1. Student’s t-test was also used in order to compare the computational performance of Q-CBR to the metric algorithm. The results shown in Table 2 indicate that Q-CBR is statistically better than the metric CBR with a certainty of at least 99%.
Performance of the CBR and Q-CBR retrieval step time in seconds, mean and standard deviation for 40 trials of 10 minutes; absolute t-value and confidence interval (in %)
Experiments with real robots were conducted with two humanoid-robots based on the Darwin-OP robot, adapted to use a computer with the same configuration of the simulation experiments. The robots have 0.55 centimeters of height and walk an average of 70 cm/min. They have 22 degrees of freedom, and are equipped with an UM6 Ultra-Miniature Orientation Sensor and a Logitech HD Pro Webcam C920. The main difference between these robots and Darwin-OP is in their chest, where the FEI humanoids carry an Intel NUC i5 with 8 GB SDRAM running Ubuntu 14.04 LTS responsible to run the code.
Results with real robots experiments (mean and standard deviation for 5 trials of 10 minutes)
Results with real robots experiments (mean and standard deviation for 5 trials of 10 minutes)
The scenario was similar to the second scenario used in the simulation experiments (Section 4.2), with the same case base and the same implementation of the qualitative and reactive approaches in the simulator. The implementation on real robots did not require significantly re-writing the code, only the vision and the control modules of the Cross architecture had to be changed. The robots were able to recognize the ball and other robots, communicate with each other and perform basic tasks such as walking, turning, kicking and passing the ball.

Sequence of actions performed by the robots.
The experiments consist of 5 trials of 10 minutes and, as in the previous experiments, the average number of goals, the number of near misses and the number of errors were considered. Table 3 presents the results of Q-CBR and the reactive algorithm. Q-CBR algorithm outperforms the reactive agent, scoring an average of 1.20 goals and 2.00 near misses, per trial, whereas the reactive agents scored 0.40 goals and had 1.16 near misses. Q-CBR has also executed an average of 17.51 retrievals per trial. Experiments were not conducted with the metric CBR algorithm due to the fact that, in contrast to the simulator, coordinates of the robots and the ball in the field are not given in the real-robot scenario. The average retrieval time was similar to the simulation (about 0.0076 seconds), although the number of goals scored could be higher with the improvement of some aspects of the robot, such as the control of walk, kick or pass. Student’s t-test was used in order to compare the performance of the proposed approach with the reactive algorithm. In this experiment, the Q-CBR is statistically better and scored more goals than the reactive approach with a certainty of at least 95%.
Figure 10 presents a sequence of actions performed by the robots during the experiments. As it can be seen, the coordinator robot walks to the ball while the executor robot waits until it receives an action. When the coordinator robot has possession of the ball, it scans for objects in the field until it finds a teammate (the executor robot). Then, the coordinator robot retrieves a case, shares the adapted position and action and, finally, passes the ball to the executor robot. The executor robot walks to the adapted position and kicks the ball to the goal.
Several CBR references can be found in the literature using cases with qualitative representation but with no relation to QSR approaches. For instance, Du, Liang and Sun [9] present an algorithm that integrates spatial relations in CBR, extracting the similarity coefficient of cases and the problem, matching each other with respect to some characteristic. The work of Liu, Fu and Zhou [20] proposes a CBR algorithm based on qualitative causality, combining metric and qualitative similarity methods to measure and retrieve a case. The work reported in the present paper uses qualitative spatial reasoning to represent the objects’ position and retrieves the most similar case based on a Conceptual Neighborhood Diagram. So, the neighborhood diagram facilitates a definition of distance between qualitative relations, that is used to calculate an adapted position for the agent.
The work presented in Jære, Aamodt and Skalle [15] uses temporal reasoning and CBR, where the cases are represented as temporal graphs and the retrieval step is performed matching the graphs and creating a similarity degree. Dufour-Lussier et al. [10] propose a method for adaptation of spatial and temporal cases during the reuse step of CBR, where the similarity between two scenarios is measured based on the distance between the considered relations. It differs from the retrieval algorithm presented in this paper since, here, each qualitative position of the objects in the cases is compared with the objects in the problem, retrieving the cases that have the minimal cost of adaptation among the cases that have the CND that is the most similar the problem’s CND.
Young and Hawes [40,41] applied the Star Calculus to represent the qualitative direction between entities on the RoboCup Soccer Keepaway [38]. In another environment, Southey and Little [37] applied QSR to games, where the objects’ position were modeled as qualitative spatial relations. The results of these papers show that the use of QSR is an interesting way to generalize the objects’ position representation. Our work uses
Conclusion and future work
This work introduced and analyzed an algorithm called Q-CBR, a case-based reasoning method assuming a qualitative spatial representation of the domain. By modeling cases in a CBR system as qualitative spatial relations, and using the notion of Conceptual Neighborhood Diagrams and cost functions as a similarity measure, a faster case-retrieval method was obtained when compared with a metric algorithm. Besides, in some domains, qualitative representation is more appropriate than numerical. The humanoid-robot soccer is one of these domains, as the robots are not capable of computing the precise positions of objects in the field.
Aiming at evaluating the method proposed in this paper, experiments were performed in a simulated environment with a small case base, using two distinct scenarios. The proposed method was also evaluated in a real humanoid-robot scenario. The results show that the teams that used Q-CBR had a higher number of scored goals and lower (more efficient) retrieval time. In all experiments executed in this work, the algorithm introduced in this paper (Q-CBR) was three times faster than the metric algorithm tested, which allows the execution of Q-CBR in robots with a limited processing power and hardware.
Future work shall consider the implementation of the complete Q-CBR cycle and the investigation of the performances related to the revision and retention processes. Given the interesting results obtained by Q-CBR, we propose to implement this work following the Goal-Driven Autonomy (GDA) model, where the agents will be able to learn, plan and reuse goal policies.
Footnotes
Acknowledgements
Thiago Pedro Donadon Homem acknowledges support from CAPES and PRP/IFSP. Danilo Hernani Perico acknowledges support from CAPES. Paulo Eduardo Santos acknowledges support from CNPq grant 307093/2014-0 and FAPESP-IBM grant 2016/18792-9. Ramon Lopez de Mantaras acknowledges support from Generalitat de Catalunya Research Grant 2014 SGR 118 and CSIC Project 201550E022. We would like to thank the reviewers for their detailed comments and suggestions on the paper, as these led us to an improvement of the work.
