Retrieving and reusing qualitative cases: An application in humanoid-robot soccer

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 $EOPRA$ formalism, are stored as qualitative cases that are applied in the definition of new retrieval and reuse algorithms. The retrieval algorithm uses a Conceptual Neighborhood Diagram to compute the similarity between a new problem and the cases in the case base, and to select the most similar case. The reuse algorithm uses a composition algorithm to calculate the adapted position of the agents based on their frame of reference. The proposed approach was evaluated on simulation and on real humanoid robots. Results suggest that this proposal is faster than using a quantitative model with a numerical similarity measurement such as the Euclidean distance. As a result of running Q-CBR, the robots obtained a higher average number of goals than those obtained when running a metric CBR approach.

Keywords

Case-Based Reasoning Qualitative Spatial Reasoning humanoid-robot

1. 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 $EOPRA$ [24] for domain modeling, whereby instead of representing cases using the Cartesian coordinate system, we represent them as qualitative orientation and distance relations. The proposed algorithms use Conceptual Neighborhood Diagrams (CND) [7,14] and a cost function to compute the similarity between a new problem and the cases in the case base, to retrieve the most similar case and to reuse its solution to solve the new problem. This work was evaluated in the robot-soccer domain, as defined by the RoboCup Federation Humanoid League [34]. In this domain, a team of humanoid robots plays a soccer game against an opponent team on an artificial grass-soccer field. Three categories separate the teams according to the robots’ heights. The robots must have a human-like body, with two legs, two arms and one head attached to a trunk. Two types of experiments were performed: the first was conducted in a simulation software, in which the proposed approach was compared to the metric-based method presented in Ros et al. [35] and to a reactive approach; the second experiment was executed with real robots, where the present proposal was compared with a reactive approach. In both experiments, the number of goals scored and the retrieval time were analyzed.

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).

2. Research background

This section presents the two methodologies that are used in this work, Case-Based Reasoning (CBR) and Qualitative Spatial Reasoning (QSR).

2.1. 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]: $\begin{matrix} (1) & case = (P, A, K), \end{matrix}$ where P is the problem description, A is the solution description and K represents the case scope.

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: $\begin{array}{rcl} P & = & {B : (x, y), R_{1} : (x_{1}, y_{1}), \dots, R_{v} : (x_{v}, y_{v}), \\ (2) & O_{1} : (x_{1}, y_{1}), \dots, O_{u} : (x_{u}, y_{u})}, \end{array}$ where B is the ball’s position, $R_{i}$ is the teammate ( $i \in {1, \dots, v}$ ) and $O_{j}$ is the opponent ( $j \in {1, \dots, u}$ ).

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 $a_{i_{k}}$ (for $i \in {1, \dots, v}$ and $k \in {1, \dots, p}$ ) assigned to each agent $R_{i}$ : $\begin{array}{rcl} A & = & {R_{1} : {a_{1_{1}}, \dots, a_{1_{p}}}, \dots, \\ (3) & R_{v} : {a_{v_{1}}, \dots, a_{v_{p}}}} . \end{array}$

The case-scope representation (K) is defined as elliptic regions around the object’s positions, with radii $τ_{O_{u}}^{x}$ and $τ_{O_{u}}^{y}$ , where the objects should be positioned in order to retrieve that case. In other words, it defines the applicability boundaries of the cases. K can be defined as: $\begin{array}{rcl} K & = & {B : (τ_{B}^{x}, τ_{B}^{y}), O_{1} : (τ_{O_{1}}^{x}, τ_{O_{1}}^{y}), \dots, \\ (4) & O_{u} : (τ_{O_{u}}^{x}, τ_{O_{u}}^{y})} . \end{array}$

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 ${EOPRA}_{m}$ formalism and the idea of Conceptual Neighborhood Diagrams.

2.2. 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 ( $OPRA$ ) [23] has been the major formalism for representing and reasoning about objects with intrinsic fronts, such as cars, boats [11,25] and robots [23]. ${OPRA}_{m}$ refers to the Oriented Point Algebra with granularity m, used in order to obtain the angular resolution, which is equal to $\frac{2 π}{2 m}$ [25]. The objects are represented as oriented points, that refer to Cartesian coordinates (x and y) and orientation (θ). Each point defines a relative reference frame of granularity m ( $m \in N$ ).

In ${OPRA}_{m}$ a relation between two oriented points A and B is represented as $A_{m} ∠_{i}^{j} B$ , which means: given the granularity m, the relative position of B with respect to A is described by i and the relative position of A with respect to B is j. The $OPRA$ formalism describes only the orientation between objects, however in several domains the distance is an important spatial information that must be considered.

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 $0 ⩽ e ⩽ 2 n$ and e must be an even number [24]. $\begin{matrix} (5) & b_{A} (e) = \{\begin{matrix} \infty & if e = 2 n, \\ \frac{e δ_{A}}{n} & if e ⩽ n, \\ \frac{n δ_{A}}{2 n - e} & otherwise. \end{matrix} \end{matrix}$

In this context, the distance relations between two points A and B are represented as $A_{n} ◯_{e}^{f} B$ , where e represents the relative distance of B with respect to A and f, the relative distance of A with respect to B.

The idea of elevated points can be combined with a directional calculus, enhancing its expressiveness. An example is $EOPRA$ [8,25] that combines the concepts of directional relations of $OPRA$ with qualitative distance as elevated points, describing the positions of objects (distance and orientation) from the point of view of an agent.

The ${EOPRA}_{m}$ notation is derived from ${OPRA}_{m}$ and it allows a joint representation of qualitative direction and distance between two points as: $A_{m}^{n} ∠_{i}^{j}_{e}^{f} B$ , where m is the orientation granularity, n is the distance granularity, i and j are orientation relations, and e and f are distance relations. A granularity parameter m allows the definition of angular zones used to represent a world discretization. Given the granularity parameter m, the world is partitioned into $4 m$ regions for each oriented object.

For notational simplicity, the distance and orientation granularity are treated as having the same value ( $n = m$ ), so the granularity m refers to qualitative orientation and distance. Figure 1 shows an example of a $EOPRA$ relation between two elevated points (A and B): $A_{4} ∠_{13}^{1}_{3}^{5} B$ representing that both A and B have been discretized into 16 orientation relations ( $4 m$ ) and 8 distance relations ( $2 m$ ). For relative orientation, A is in the sector 1 of B and B is in the sector 13 of A, and for relative distance, A is in the sector 5 of B and B is in the sector 3 of A.

Fig. 1.

${EOPRA}_{4}$ relation $A_{4} ∠_{13}^{1}_{3}^{5} B$ .

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.

3. Problem formulation

This section presents the Qualitative Case-Based Reasoning (Q-CBR) method, the qualitative spatial modeling for the cases, the CND of ${EOPRA}_{m}$ and the description of the use of CND as a tool for similarity measuring, defining a new retrieval algorithm for CBR.

3.1. Qualitative direction and distance

This work uses ${EOPRA}_{m}$ to represent the relations between any two objects in the RoboCup domain as a tuple of orientation and distance. Based on the work of Moratz and Wallgrün [24] and Dorr, Latecki and Moratz [8], we have considered the viewpoint orientation as being the front of the agent and the granularity parameter $m = 6$ , creating 24 direction sectors. These direction sectors are grouped into 8 regions: left (l), right (r), front (f), back (b), left-front (lf), right-front (rf), left-back (lb) and right-back (rb). Figure 2 shows the direction sectors and regions defined, where each region is composed of three sectors. We have considered that left-front, right-front, left-back and right-back are transition regions, so they have a smaller angular region.

Considering an environment of length 9.00 meters and width 6.00 meters (a robot-soccer field), a granularity parameter of $n = 6$ was assumed defining 12 distance sectors, numbered from 0 to 11. These distance sectors are then grouped into 6 categories: at (a), very close (vc), close (c), far (f), very far (vf) and farthest (ft). Figure 3 shows the distance regions created. Based on Moratz and Wallgrün [24], and considering the agent’s height (0.55 meters), the regions were defined with respect to the observer, such that at refers to an object placed closer than 0.33 meters, very close refers to an object placed between 0.33 and 0.66 meters, close represents an object placed between 0.66 and 1.00 meter, far refers to an object placed between 1.00 and 1.50 meters, very far is related to an object placed between 1.50 and 3.00 meters, and farthest refers to an object at more than 3.00 meters.

Fig. 2.

Qualitative orientation representation.

Fig. 3.

Qualitative distance representation.

In this work we consider a granularity parameter of $m = n = 6$ (to both the distance and direction partitions), defining ${EOPRA}_{6}$ , as presented in Fig. 4. ${EOPRA}_{6}$ is composed of 48 qualitative regions plus one, labeled equal (EQ), at the center of the relations, corresponding to the observer’s position. A Conceptual Neighborhood Diagram for ${EOPRA}_{6}$ is shown in Fig. 5. In this paper we consider a cost of 1 for each transition between adjacent relations in this CND.

Fig. 4.

Qualitative relations for distance and orientation.

Fig. 5.

CND of the proposed ${EOPRA}_{6}$ representation.

The notion of similarly and CND in the work of Randell and Witkowski [32] can be used to define a distance function ${Dmin}_{ϕ} (X_{1}, X_{2})$ that takes two spatial relations $X_{1}$ and $X_{2}$ and maps them to the minimum CND (node to node) distance. In other words, ${Dmin}_{ϕ} (X_{1}, X_{1}) = 0$ , ${Dmin}_{ϕ} (X_{1}, X_{2}) > 0$ if and only if $X_{1} \neq X_{2}$ [32]. Using the distance function, the CND can be presented as a similarity matrix, in which the minimal CND distance can be computed using any algorithm to find the shortest path between nodes in a graph, such as Dijkstra’s algorithm [4]. In this work, the CND of ${EOPRA}_{6}$ resulted in a similarity matrix with the minimal path (distance) between each 49 relations, allowing a fast case comparison during the retrieval step.1

The distance matrix for ${EOPRA}_{6}$ is available at the URL http://fei.edu.br/~rbianchi/images/distancematrix.jpg.

3.2. Qualitative case representation

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: $\begin{matrix} (6) & C = (P, A) . \end{matrix}$

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: $\begin{array}{rcl} P & = & {R_{1} : [B, R_{1}, \dots, R_{v}, O_{1}, \dots, O_{u}], \dots, \\ (7) & R_{v} : [B, R_{1}, \dots, R_{v}, O_{1}, \dots, O_{u}]}, \end{array}$ where B is the qualitative ball’s position, v is the number of robots that take part in the case solution (teammates), u is the number of opponents, $R_{i}$ is the qualitative relation between the current agent and the teammate i ( $i \in {1, \dots, v}$ ) and $O_{j}$ is the qualitative relation between current agent and the opponent j ( $j \in {1, \dots, u}$ ).

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].

3.3. 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: $\begin{array}{rcl} {Dist}_{Q} (p, c) & = & {Dmin}_{ϕ} (B^{c}, B^{p}) \\ + \sum_{i = 1}^{v} {Dmin}_{ϕ} (R_{i}^{c}, R_{i}^{p}) \\ (8) & + \sum_{j = 1}^{u} {Dmin}_{ϕ} (O_{j}^{c}, O_{j}^{p}), \end{array}$ where v is the number of robots that take part in the case solution (teammates), u is the number of opponents, $B^{c}$ is the qualitative position of the ball in the case, $B^{p}$ is the ball’s qualitative position in the problem, $R_{i}^{c}$ is the qualitative position of each teammate robot i in the case, $R_{i}^{p}$ is the qualitative position of teammate robot i in the given problem, $O_{j}^{c}$ is the qualitative position of each opponent j in the case and $O_{j}^{p}$ the opponent j qualitative position in the problem.

The distance function is used to calculate case similarity by means of the qualitative similarity function defined by: $\begin{array}{l} {Sim}_{Q} (p, c) \\ = \frac{{CND}_{MaxDist} \times (1 + v + u) - {Dist}_{Q} (p, c)}{{CND}_{MaxDist} \times (1 + v + u)}, \\ (9) \end{array}$ where v and u are as defined in the qualitative distance function and ${CND}_{MaxDist}$ is the maximum distance between two objects in the CND. The result is normalized.

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. $\begin{array}{l} (10) & {Cost}_{Q} (p, c) = \sum_{i = 1}^{v} {Dmin}_{ϕ} (R_{i}^{c}, R_{i}^{p}), \end{array}$ where v is the number of robots that take part in the case solution, $R_{i}^{c}$ is the qualitative position of each robot i in the case and $R_{i}^{p}$ is the qualitative position of robot i in the problem. The adaptation cost function includes only robots that are in the agent’s team, meaning that their position can be controlled (i.e., adapted). The adaptation cost is the cost to move the robots of the team to the position that is described in the most similar candidate case, and it reflects how much this adaptation costs.

Algorithm 1 represents the proposed retrieval method based on the CND distance measure and adaptation cost. This algorithm has two lists: $sim_candidates$ which contains cases whose similarity value is greater than a $threshold$ ; and the list $adapt_candidates$ that is used to compute the adaptation cost of the candidate cases, sorted in ascending cost order. Lines 2–11 of Algorithm 1 search for candidate cases in the entire case base. Line 3 measures the qualitative similarity from problem to case using Equation (9). In lines 4–5, if there is a case equal to the problem, the function returns the case and ends the search. If no case is found within the similarity range allowed, a pre-defined reactive case is returned (lines 12–13). A reactive case consists of a naïve behavior, in which the robot searches for the ball, walks toward it, aligns itself with respect to the opposing goal and kicks the ball forward. Lines 15–20 compute the cost of adaptation of each case found in the previous steps. The list of cases is sorted by the adaptation cost, and the case with the lowest adaptation cost is returned ( $sim_value$ is the second sort criteria).

Algorithm 1

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 ( $v = 1$ ) and three objects, for instance two opponent robots and one ball ( $u = 3$ ), where the teammate is the only object that can be adapted in the case. According to the distance matrix, ${CND}_{MaxDist}$ is equal to 8.

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 $(f, vc)$ , the teammate is placed to the left and far from the robot $(l, f)$ , one opponent positioned on the left and close to the robot $(l, c)$ and another opponent positioned on the right-front and far from the reference robot $(rf, f)$ .

After running the retrieval algorithm the result is: (a) case #1 (top-right) with ${Dist}_{Q} = 6$ , ${Sim}_{Q} = 0.8125$ and ${Cost}_{Q} = 1$ ; (b) case #2 (bottom-left) with ${Dist}_{Q} = 0$ , ${Sim}_{Q} = 1$ and ${Cost}_{Q} = 0$ ; (c) case #3 (bottom-right) with ${Dist}_{Q} = 2$ , ${Sim}_{Q} = 0.9375$ and ${Cost}_{Q} = 0$ . In this example, case #2 will be retrieved because it has ${Sim}_{Q} = 1$ , but if case #2 would be discarded, case #3 could be retrieved since it has the lowest adaptation cost.

Fig. 6.

Example of stored cases and case retrieval.

3.4. Qualitative case reuse

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 ( $R_{coord}$ ), which coordinates the retrieval and reuse steps, the executor robot ( $R_{exe}$ ), a robot that is part of the solution, and a retrieved robot ( $R_{ret}$ ), a virtual robot which represents the $R_{exe}$ ’s position of the retrieved case.

Algorithm 2 presents the proposed reuse method, that focuses on calculating how the $R_{exe}$ can reach the $R_{ret}$ ’s position, and the actions it must perform to reach this position. As the retrieved case contains the qualitative position of the coordinator robot’s point of view, it needs to be converted to the executor robot’s point of view, that has its own qualitative relations about the world. Considering ${executors}_{robot}$ as a list of controllable robots, r as a robot identifier and $coord$ as the coordinator robot identifier (the robot closest to the ball), the algorithm receives the problem and the retrieved case and, for each robot that is part of the solution, an adapted position is generated based on the executor robot’s point of view (line 3). Line 4 shares with the executor robot the adapted positions and line 5 shares the actions it must perform to solve the problem.

Algorithm 2

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 $R_{exe}$ to $R_{ret}$ .

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 ( $R_{coord}$ ), executor robot ( $R_{exe}$ ) and the robot in the case ( $R_{ret}$ ). Line 3 infers a set of ${OPRA}_{m}$ relations and line 4 restricts the set of possible $\hat{s}$ relations by means of triangulation. These functions are presented by Algorithms 4 and 5, respectively.

Finally, line 5 calculates the rough distance between $R_{coord}$ , $R_{exe}$ and $R_{ret}$ and discretizes it into qualitative distances, as presented in Section 3.1, and returns (line 6) the qualitative orientation and distance that the $R_{exe}$ must to adapt.

Algorithm 3

Composition Algorithm

Function $OpraInference$ , used in Algorithm 3 and described in Algorithm 4, uses the ${OPRA}_{m}$ algorithm proposed by Mossakowski and Moratz [25]. Let i, j, k and l be known object relations and s and t be unknown relations. Given a set of relations between the objects A, B and C, where $A_{m} ∠_{i}^{j} B$ , $B_{m} ∠_{k}^{l} C$ and $A_{m} ∠_{s}^{t} C$ , the algorithm infers the set of possible directions, i.e., it checks which values s can assume when t is given; or which values of s and t can assume when t is not given, and returns all compositions that hold. By relations, we consider the sectors created after the world discretization, i.e., $m = 6$ generates 24 relations.

Algorithm 4

${OPRA}_{m}$ – Inferring the set of relations $\hat{s}$ or $\hat{s}$ and $\hat{t}$ of ${OPRA}_{m}$ for non-coincident points

Lines 5 and 14 (Algorithm 4) compute the composition of $OPRA$ relations as defined by Mossakowski and Moratz [25]: $\begin{matrix} (11) & \begin{matrix} opra (_{m} ∠_{i}^{j},_{m} ∠_{k}^{l},_{m} ∠_{s}^{t}) iff \\ \exists 0 ⩽ u, v, w < 4 m . {turn}_{m} (u, - i, s) \\ \land {turn}_{m} (v, - k, j) \land {turn}_{m} (w, - t, l) \\ \land {triangle}_{m} (u, v, w) . \end{matrix} \end{matrix}$

According to [25], ${turn}_{m} (a, b, c)$ detects complete turns, while ${triangle}_{m} (a, b, c)$ detects a triangle by means of the sum of the angles and the comparison of the sign of the angles ( ${sign}_{m} (d)$ ). A triangle is verified as: $\begin{matrix} (12) & \begin{matrix} {triangle}_{m} (a, b, c) iff \\ {turn}_{m} (a, b, c - 2 m) \land (a, b, c) \\ \neq (2 m, 2 m, 2 m) \\ \land {sign}_{m} (a) = {sign}_{m} (b) = {sign}_{m} (c) . \end{matrix} \end{matrix}$

Equation (13) verifies a complete turn and Equation (14) returns the sign of an angle, as: $\begin{array}{l} (13) & \begin{matrix} {turn}_{m} (a, b, c) iff \\ | ((a + b + c + 2 m) mod 4 m) - 2 m | \\ ⩽ (a mod 2 m) \times (b mod 2 m), \end{matrix} \\ (14) & {sign}_{m} (d) = \{\begin{matrix} 0, & if (d mod 4 m = 0) \\ \lor (d mod 4 m = 2 m), \\ 1, & if (d mod 4 m < 2 m), \\ - 1, & otherwise . \end{matrix} \end{array}$

Using triangulation, Algorithm 5 reduces the number of possible relations in the disjunction, resulting in a qualitative direction. ${OPRA}_{m}$ algorithm and the used functions are well-defined by referred authors.

Algorithm 5

Triangulation – Restricting the set of $\hat{s}$ relations by triangulation

In order to exemplify the reuse step using CA, Fig. 7 presents the coordinator robot’s ( $R_{coord}$ ) point of view about the executor robot’s ( $R_{exe}$ ) qualitative position, the robot’s position on the retrieved case ( $R_{ret}$ ), and the executor robot’s point of view about the coordinator robot’s qualitative position. $R_{coord}$ can easily obtain the angle β, so it can calculate the angle α using the law of cosines. After obtaining α, the angle is discretized according ${OPRA}_{6}$ definitions, representing the $R_{exe}$ ’s qualitative orientation to the $R_{ret}$ position. The $R_{exe}$ ’s qualitative distance is calculated by the Pythagorean theorem and the distance is discretized according ${EOPRA}_{6}$ . In Fig. 7 (left) the $R_{coord}$ searches for the objects’ position on the environment and finds the $R_{exe}$ ’s position in left, farthest; it retrieves a case and selects the most similar case where the robot’s position in the case is front, very far ( $R_{ret}$ ). Figure 7 (center), by running the Composition Algorithm, the adapted position to the $R_{exe}$ ’s point of view is obtained, returning the regions right-front, farthest that are shared among the agents. Figure 7 (right) shows that $R_{exe}$ executes the movements to reach $R_{ret}$ ’s position and performs the actions to solve the problem.2

The direction and distance labels were hidden to allow clear visualization.

Fig. 7.

Example of Reuse step using Composition Algorithm: changing frame of reference.

4. Experiments and results

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.

4.1. 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.

Fig. 8.

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 $C + +$ . This simulator has distinct control and vision processes for simulation and real robots experiments, but decision, planning and localization code is shared between both types of experiments. The simulator environment is a soccer field that obeys the RoboCup Humanoid Kidsize rules [34].

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 http://fei.edu.br/~rbianchi/software.html. Some videos of simulation and experiments with real robots can be found at https://goo.gl/nquuKc.

4.2. Experiments in the simulator

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.

Fig. 9.

Two scenarios created for simulated experiments.

Table 1

Results of simulation experiments (mean and standard deviation for 40 trials of 10 minutes)

Scenario	Method	Goals	t-value	Near misses	t-value	Errors	t-value
#1	CBR	$2.58 \pm 1.18$	1.63 (90%)	$2.45 \pm 1.22$	7.72 (99%)	$2.93 \pm 1.23$	5.39 (99%)
	Q-CBR	$2.98 \pm 1.01$	1.63 (90%)	$0.73 \pm 0.71$	7.72 (99%)	$1.58 \pm 0.99$	5.39 (99%)
	Reactive	$0.33 \pm 0.52$	–	$2.08 \pm 1.15$	–	$3.88 \pm 1.54$	–
#2	CBR	$2.55 \pm 1.53$	1.69 (95%)	$2.65 \pm 1.24$	2.43 (99%)	$2.78 \pm 1.06$	4.92 (99%)
	Q-CBR	$3.10 \pm 1.37$	1.69 (95%)	$2.03 \pm 1.06$	2.43 (99%)	$1.73 \pm 0.84$	4.92 (99%)
	Reactive	$0.48 \pm 0.71$	–	$1.78 \pm 1.06$	–	$3.53 \pm 2.09$	–

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 $\pm 135 °$ , discarding the region named as back. This limitation does not change the discretization of the world and the problem formulation presented in Section 3 remains the same.

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%.

Table 2

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 %)

Scenario	Method	Retrieval (seconds)	t-value
#1	CBR	$0.0218 \pm 0.0042$	19.902 (99%)
#1	Q-CBR	$0.0076 \pm 0.0017$	19.902 (99%)
#2	CBR	$0.0228 \pm 0.0040$	22.746 (99%)
#2	Q-CBR	$0.0075 \pm 0.0014$	22.746 (99%)

4.3. Experiments with real robots

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.

Table 3
Results with real robots experiments (mean and standard deviation for 5 trials of 10 minutes)

Method Goals Near misses Errors

Q-CBR $1.20 \pm 0.75$ $2.00 \pm 1.41$ $2.80 \pm 1.16$

Reactive $0.40 \pm 0.49$ $1.16 \pm 1.16$ $2.60 \pm 1.02$

Method	Goals	Near misses	Errors
Q-CBR	$1.20 \pm 0.75$	$2.00 \pm 1.41$	$2.80 \pm 1.16$
Reactive	$0.40 \pm 0.49$	$1.16 \pm 1.16$	$2.60 \pm 1.02$

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.

Fig. 10.

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.

5. Related work

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 $EOPRA$ and compares its retrieval time with respect to a metric-based algorithm. We also performed experiments on real robots, with limited view of the environment.

6. 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.

References

Aamodt and

Plaza, Case-based reasoning: Foundational issues, methodological variations, and system approaches, AI Communications7 (1994), 39–59.

M.M.

Altaf,

B.M.

Elbagoury,

Alraddady and

Roushdy, Extended case-based behavior control for multi-humanoid robots, International Journal of Humanoid Robotics13 (2016), Article ID 1550035. doi:10.1142/S0219843615500358.

A.G.

Cohn and

Renz, Qualitative spatial representation and reasoning, in: Handbook of Knowledge Representation, Elsevier, 2008, pp. 551–596.

T.H.

Cormen,

C.E.

Leiserson,

R.L.

Rivest and

Stein, Introduction to Algorithms, 2nd edn, MIT Press, 2001.

Davoust,

M.W.

Floyd and

Esfandiari, Use of Fuzzy Histograms to Model the Spatial Distribution of Objects in Case-Based Reasoning, Springer, Berlin, 2008, pp. 72–83.

R.L.

de Mántaras,

McSherry,

Bridge,

Smyth,

Craw,

Faltings,

M.L.

Maher,

Cox,

Forbus,

Keane,

Aamodt and

Watson, Retrieval, reuse, revision, and retention in CBR, The Knowledge Engineering Review20 (2006), 215–240.

N.V.

De Weghe and

De Maeyer, Conceptual neighbourhood diagrams for representing moving objects, in: Perspectives in Conceptual Modeling, LNCS, Vol. 37702005, pp. 1–11. doi:10.1007/11568346_1.

C.H.

Dorr,

L.J.

Latecki and

Moratz, Shape similarity based on the qualitative spatial reasoning calculus eOPRAm, in: 12th COSIT 2015, Proceedings, Santa Fe, NM, USA,

S.I.

Fabrikant,

Raubal,

Bertolotto,

Davies,

Freundschuh and

Bell, eds, Springer, 2015, pp. 130–150.

Du,

Liang and

Sun, Integrating spatial relations into case-based reasoning to solve geographic problems, Knowledge-Based Systems33 (2012), 111–123. doi:10.1016/j.knosys.2012.03.002.

10.

Dufour-Lussier,

Le Ber,

Lieber and

Martin, Adapting spatial and temporal cases, in: Proceedings of 20th ICCBR 2012, Lyon, France, September 3–6, 2012,

B.D.

Agudo and

Watson, eds, Springer, 2012, pp. 77–91.

11.

Dylla, Qualitative spatial reasoning for navigating agents: Behaviour monitoring and interpretation – Ambient assisted living, in: Ambient Intelligence and Smart Environments, IOS Press, Amsterdam, 2009, pp. 98–128, Chapter 3.

12.

M.W.

Floyd,

Esfandiari and

Lam, A case-based reasoning approach to imitating robocup players, in: Proceedings of the Twenty-First FLAIRS, Coconut Grove, FL, USA

Wilson and

H.C.

Lane, eds, AAAI Press, 2008, pp. 251–256.

13.

A.U.

Frank, Qualitative spatial reasoning about cardinal directions, in: Proceedings of Auto-Carto 10 ACSM-ASPRS, Vol. 6, 1991, 148–167.

14.

Freksa, Conceptual neighborhood and its role in temporal and spatial reasoning, in: Decision Support Systems and Qualitative Reasoning, 1991, pp. 181–187.

15.

M.D.

Jære,

Aamodt and

Skalle, Representing temporal knowledge for case-based prediction, in: Proceedings of 6th ECCBR 2002, Aberdeen, Scotland, UK, September 4–7, 2002, 2002, pp. 174–188.

16.

Karol,

Nebel,

Stanton and

Williams, Case based game play in the robocup four-legged league: Part I the theoretical model, in: RoboCup, LNCS, Vol. 3020, Springer, 2003, pp. 739–747.

17.

Kolodner, Case-Based Reasoning, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1993.

18.

Ligozat, Qualitative Spatial and Temporal Reasoning, John Wiley & Sons, Inc., Hoboken, NJ, USA, 2013.

19.

Lin,

Liu and

Chen, A hybrid architecture of case-based reasoning and fuzzy behavioral control applied to robot soccer, in: Workshop on AI (ICS2002), Hualien, Taiwan, 2002.

20.

Liu,

Fu and

Zhou, Case-based reasoning algorithm based on qualitative causality, in: 2014 Seventh International Joint Conference on CSO, IEEE, 2014, pp. 519–523.

21.

Marling,

Tomko,

Gillen,

Alex and

Chelberg, Case-based reasoning for planning and world modeling in the robocup small sized league, in: IJCAI Workshop on Issues in Designing Physical Agents for Dynamic Real-Time Environments: World Modelling, Planning, Learning, and Communicating, 2003, pp. 29–36.

22.

A.P.

Martin,

P.E.

Santos and

Safi-Samghabad, Consistency check in a multiple viewpoint system reasoning about occlusion, in: The 30th International Conference on Industrial, Engineering, Other Applications of Applied Intelligent Systems, Springer, 2017, pp. 523–532.

23.

Moratz, Representing relative direction as a binary relation of oriented points, in: 17th ECAI,

Brewka,

Coradeschi and

Perini, eds, IOS Press, 2006, pp. 407–411.

24.

Moratz and

J.O.

Wallgrün, Spatial reasoning with augmented points: Extending cardinal directions with local distances, Journal of Spatial Information Science5(5) (2012), 1–30.

25.

Mossakowski and

Moratz, Qualitative reasoning about relative direction of oriented points, Artificial Intelligence180(181) (2012), 34–45. doi:10.1016/j.artint.2011.10.003.

26.

Nehmzow, Scientific Methods in Mobile Robotics: Quantitative Analysis of Agent Behaviour, Springer-Verlag, 2006.

27.

D.H.

Perico,

R.A.C.

Bianchi,

P.E.

Santos and

R.L.

de Mántaras, Collaborative communication of qualitative spatial perceptions for multi-robot systems, in: Proceedings of the 29th International Workshop on Qualitative Reasoning (IJCAI), New York, NY, USA, 2016, pp. 77–84.

28.

D.H.

Perico,

T.P.

Homem,

A.C.

Almeida,

I.J.

Silva,

C.O.

Vilao,

V.N.

Ferreira and

R.A.

Bianchi, A robot simulator based on the cross architecture for the development of cognitive robotics, in: XIII LARS/SBR, IEEE, 2016, pp. 317–322.

29.

D.H.

Perico,

I.J.

Silva,

T.P.D.

Homem,

R.C.

Destro and

R.A.C.

Bianchi, Hardware and software aspects of the design and assembly of a new humanoid robot for robocup soccer, in: 2014 SBR-LARS, IEEE, 2014, pp. 73–78.

30.

Randell,

Witkowski and

Shanahan, From images to bodies: Modelling and exploiting spatial occlusion and motion parallax, in: IJCAI, 2001, pp. 57–63.

31.

D.A.

Randell,

Cui and

A.G.

Cohn, A spatial logic based on regions and connection, in: 3rd International Conference on Knowledge Representation and Reasoning, Morgan Kaufmann, 1992, pp. 165–176.

32.

D.A.

Randell and

Witkowski, Tracking regions using conceptual neighbourhoods, in: Proceedings of the Workshop on Spatial and Temporal Reasoning ECAI 2004, 2004, pp. 63–71.

33.

Renz and

Mitra, Qualitative direction calculi with arbitrary granularity, in: Proceedings of PRICAI 2004, Springer, Berlin, 2004, pp. 65–74.

34.

RoboCup, 2015 RoboCup soccer humanoid league rules and setup, 2015, http://www.robocuphumanoid.org.

35.

Ros,

J.L.

Arcos,

R.L.

de Mantaras and

Veloso, A case-based approach for coordinated action selection in robot soccer, Artificial Intelligence173(9–10) (2009), 1014–1039. doi:10.1016/j.artint.2009.02.004.

36.

P.E.

Santos,

Ligozat and

Safi-Samghabad, An occlusion calculus based on an interval algebra, in: 2015 Brazilian Conference on Intelligent Systems (BRACIS), 2015, pp. 128–133. doi:10.1109/BRACIS.2015.12.

37.

Southey and

J.J.

Little, Learning qualitative spatial relations for object classification, in: IROS 2007 Workshop: From Sensors to Human Spatial Concepts, 2007.

38.

Stone,

R.S.

Sutton and

Kuhlmann, Reinforcement learning for RoboCup soccer keepaway, Adaptive Behavior13(3) (2005), 165–188. doi:10.1177/105971230501300301.

39.

Wolter and

Wallgrün, Qualitative spatial reasoning for applications: New challenges and the SparQ toolbox, in: Qualitative Spatio-Temporal Representation and Reasoning: Trends and Future Directions, 2012, pp. 336–362. doi:10.4018/978-1-61692-868-1.ch011.

40.

Young and

Hawes, Predicting situated behaviour using sequences of abstract spatial relations, in: AAAI 2013 Fall Symposium Series, 2013.

41.

Young and

Hawes, Learning by observation using qualitative spatial relations, in: Proceedings of the 2015 AAMAS, Richland, SC, USA, 2015, pp. 745–751.

Retrieving and reusing qualitative cases: An application in humanoid-robot soccer

Abstract

Keywords

1. Introduction

2. Research background

2.1. Case-Based Reasoning

2.2. Qualitative Spatial Reasoning

3.1. Qualitative direction and distance

3.3. Qualitative case retrieval

4.1. RoboFEI Humanoid Soccer Simulator

Table 3 Results with real robots experiments (mean and standard deviation for 5 trials of 10 minutes) Method Goals Near misses Errors Q-CBR 1.20 ± 0.75 2.00 ± 1.41 2.80 ± 1.16 Reactive 0.40 ± 0.49 1.16 ± 1.16 2.60 ± 1.02

6. Conclusion and future work

Footnotes

Acknowledgements

References

Table 3
Results with real robots experiments (mean and standard deviation for 5 trials of 10 minutes)

Method Goals Near misses Errors

Q-CBR $1.20 \pm 0.75$ $2.00 \pm 1.41$ $2.80 \pm 1.16$

Reactive $0.40 \pm 0.49$ $1.16 \pm 1.16$ $2.60 \pm 1.02$