         A swarm of Mini-MEs: reasoning and
         information aggregation in ubiquitous
                 multi-agent contexts

           Floriano Scioscia, Michele Ruta, and Eugenio Di Sciascio

            Politecnico di Bari, via E. Orabona 4, I-70125 Bari, Italy
        E-mail: (ﬂoriano.scioscia, michele.ruta, eugenio.disciascio)@poliba.it


      Abstract. Collaborative paradigms are essential in ubiquitous comput-
      ing. Swarm intelligence can deal with complex problems deriving from
      the intrinsically unpredictable nature of mobile and pervasive scenarios.
      This paper introduces a novel reasoning framework for information fu-
      sion in multi-agent systems, encompassing a data dissemination protocol
      and non-standard, non-monotonic inference services. It enables agents
      to integrate detected and received information in a coherent view. Its
      properties include reconciliation of inconsistencies, quick adaptation to
      changes and robustness against spurious events. The paper presents the
      above generalized framework along with an experimental evaluation of a
      prototypical implementation supported by a swarm of pico-reasoners.


1   Introduction and motivation
The increasing eﬀectiveness and computing capabilities of mobile and embedded
devices allow to process and exchange rich and structured information in a novel
range of applications. More and more eﬀort is being spent to enhance ﬂexibility
and autonomy of ubiquitous and pervasive systems for information management,
dissemination and discovery. Nevertheless, both studies and technological issues
reveal that classical approaches based on centralized control and processing are
troublesome in such scenarios [11]. So Multi-Agent Systems (MAS) are often tar-
geted to provide the needed organizational support. This could be particularly
true for the so-called Semantic Web of Things (SWoT) [12], a novel paradigm
reﬂecting the convergence of Semantic Web and the Internet of Things. In an
articulated eﬀort aiming to tie metadata to ordinary objects and environments,
MAS allow ﬂexible interaction patterns and distributed information manage-
ment, able to drive complex behaviors through swarm intelligence [6]. SWoT
powers a plethora of motley micro-devices to convey small amounts of informa-
tion each. High-level semantic languages cope with interoperability issues, also
enabling machine-understandability. Non-monotonic reasoning is exploited to
deal with the evolving and even partially conﬂicting knowledge. Unfortunately,
no frameworks still exist for semantic-based information fusion integrating agent
interactions suitably for ubiquitous contexts.
    This paper introduces a novel semantic-based approach for information fusion
in ubiquitous MAS. It exploits non-standard, non-monotonic reasoning allowing
2

agents to integrate captured and received knowledge in a coherent view. A new
complex inference service has been deﬁned for this purpose, capable of manag-
ing inconsistencies in information acquired by diﬀerent agents. The framework
leverages and extends the Mini-ME mobile matchmaker reasoning services [10].
A data dissemination protocol enables agents to receive, augment and propagate
knowledge in a chain, increasing accuracy of situation awareness progressively.
Reconciliation of conﬂicts, quick adaptation to changes and robustness against
spurious events are among its properties. An experimental performance evalu-
ation was executed on a network simulator to early assess the feasibility of the
proposal.
    The remainder of the paper is organized as follows. Next section discusses
related work. Section 3 describes in detail the proposed framework, while Section
4 reports on the performance tests. Final remarks are in Section 5.


2   Related work

Multi-agent information fusion. Several approaches exist for distributed in-
formation aggregation in agent networks and MAS. When dealing with numerical
data only, aggregation functions [3, 7, 4] provide a way to fuse measurements of
individual agents and to reduce the size of exchanged data. In this family, dis-
tributed particle filtering [5] is one of the most popular and versatile techniques.
    Semantic-based multi-agent intelligence relies on operators and inference ser-
vices for information fusion on formulas. Peer-to-peer information integration in
[2] was based on epistemic logic, allowing both a parallel and a sequential pro-
cessing. Nevertheless, the approach focused on schema mappings in order to
query a heterogeneous P2P system as a single entity, while the idea proposed
here concerns distributed intelligence, with each peer having some relevant in-
formation to act upon and to exchange with the others. Such contexts require
the capability to retract consequences when new conﬂicting knowledge becomes
available. Therefore Subsumption and Satisﬁability classical inference services
are not enough: non-monotonic reasoning is needed. Belief merging and revision
[7] have been studied for a long time, with many relevant theoretical results.
Reasoning services. In particular, in [8] the Concept Abduction Problem
(CAP) has been deﬁned for Description Logics (DLs) to provide an explanation
when Subsumption does not hold. A CAP is presented as in what follows: given a
DL language L, an ontology T in L and two concepts C and D satisﬁable in T , if
T ̸|= C ⊑ D, then ﬁnd a concept H (for Hypothesis) such that T |= C ⊓ H ⊑ D.
That is, H is a possible explanation why resource features do not imply requested
ones. On the other hand, if the conjunction C ⊓ D is unsatisﬁable w.r.t. the
ontology, one can retract some requirements G (for Give up) from D to obtain a
concept K (for Keep) such that K ⊓C is satisﬁable in T . This is called a Concept
Contraction Problem (CCP) [8]. For both CAP and CCP, some minimality
criteria must be deﬁned [8], since one usually wants to hypothesize and give up
as few things as possible. Abduction and Contraction were studied and applied
to semantic matchmaking, which is basically the process of ﬁnding best matches
                                                                                 3

of a request (named D in the above deﬁnitions) among available resource ads
(named C above), where both the request and the ads are annotated w.r.t.
a reference ontology [8]. In such scenarios, under the Open World Assumption
(OWA: what is not specified has not to be interpreted as a constraint of absence),
the result is a list of ads ranked by semantic proximity. Interestingly, ads could
contain features which the user did not know or consider when composing her
request, but which could be added in a query reﬁnement process to improve
the outcome. For this purpose, the Bonus inference service was deﬁned [8] to
extract a concept B from D which denotes something that the ad oﬀers even
though the request did not ask for it. Finally, the proposed information fusion
framework requires a way to subtract information in a description from another
one. This is accomplished by means of the Concept Diﬀerence reasoning service
[14]. Also for Diﬀerence many valid solutions exist, but a maximality criterion
should be adopted in this case (i.e., subtract as much as possible).


3   Reasoning for multi-agent system intelligence

The proposed framework refers to a swarm of independent agents exchanging
annotated envelopes. Each envelope contains the sender’s current knowledge of
the context, expressed in a DL language w.r.t. a shared reference ontology. Basi-
cally, envelopes are composed of a timestamp and a 4-tuple of annotations, with
meaning as in Table 1. The juxtaposition of the four elements allows informa-
tion aggregation with reconciliation of inconsistencies through a collaborative
protocol for information dissemination, exploiting a properly devised inference
service. The protocol assigns a Time To Live (TTL) to all envelopes. An enve-
lope expires and an agent discards it when the sum of its timestamp and TTL
exceeds the agent’s current time.
    When an agent completes a data gathering and annotation round, it has
available a semantic expression N representing newly detected information. Fur-
thermore, a cache stores the most recent incoming envelope and, when a new
envelope is received, the former one is discarded. In the protocol, three basic
cases are distinguished:
1. Generation: it occurs if an agent generates an annotation and it has no fresh
(i.e., non-expired) envelope in its cache, that is when either it has received no
envelopes or all received envelopes have expired.
2. Relay: it occurs if an agent has an envelope in its cache and it is not able to

         Table 1: Meaning of the annotations in exchanged envelopes

Name         Description
C (Conﬁrmed) elements observed by both the sender and other agents
X (Clash)    elements observed by the sender, inconsistent with observations by others
M (My)       elements observed by the sender, but not by other agents
E (External) elements observed by other agents, but not by the sender
4


    Fig. 1: New envelope generation
                                                Fig. 2: Relay of a envelope

produce a semantic annotation of its own.
3. Integration and relay: it occurs when an agent has a received envelope in its
cache, which must be fused with self-detected information before transmitting
the updated snapshot of the environment.
In any case, the result is a new envelope P ′ , which will be sent in broadcast.
    In the above case 1, the resulting P ′ is sketched in Figure 1. Since everything
is the outcome of observations of the sending agent, the annotation N will be
placed in the envelope ﬁeld M , while other ﬁelds will be set to ⊤ (Top or Thing)
to denote the most generic possible observation. Conversely, in case 2 the agent
has to relay a received envelope P , therefore the result P ′ will contain only
observations made by other agent(s). The outgoing envelope is structured as in
Figure 2: only the E ﬁeld will be populated with the conjunction of the four
annotations in P ; the remaining ones will be set to ⊤.
    The last case requires the fusion of generated and received information. For
this purpose, a novel inference service was devised, so as to preserve the semantics
of the ﬁelds of both input and output envelopes. The logic problem to solve is
named Concept Integration and is formalized as:
Definition 1. Let L be a DL language, T a set of axioms in L, N a concept
expression in Land P a 4-tuple of concept expressions ⟨C, X, M, E⟩ in L, where
N is the current knowledge of agent A′ , P is knowledge accumulated by agent A
–whose components have the semantics in Table 1– and N, C, X, M, E are satis-
fiable in T . A Concept Integration Problem (CIP), identified by ⟨L, N, P, T ⟩, is
finding a 4-tuple of concept expressions P ′ = ⟨C ′ , X ′ , M ′ , E ′ ⟩, which is the inte-
gration of N and P , having the semantics in Table 1. Then P ′ is the integration
of N and P and represents knowledge accumulated by agent A′ .
Algorithm 1 solves a CIP exploiting the Concept Contraction, Abduction, Dif-
ference and Bonus inference services. At line 3, J1 = C ⊓ X ⊓ M ⊓ E is the
“resource” and N the “request”, therefore GN is the part of the observation
of agent A′ which contradicts previous observations accumulated by A, while
KN contains the part that is in accordance. Analogously for the CAP at line
4, result HN is something only A′ has detected and previous observations had
not reported. To determine what is shared by A and A′ , it is needed to subtract
HN from KN , computing the Concept Diﬀerence at line 5. Now GN and HN
clearly have the required meaning of elements X ′ and M ′ of the new envelope,
respectively (lines 6-7). Finally, in order to compute what other agents had seen
but A′ has not, the Bonus service is adopted (line 8): it is important to note
that in this case the role of “resource” is played by J2 = C ⊓ X ⊓ M only.
Including E in J2 would imply a perpetual propagation of concepts in E when
                                                                                           5

Algorithm 1 Concept Integration Problem solution
Algorithm: Integrate(⟨L, N, P, T ⟩)
Require: ⟨L, N, P = ⟨C, X, M, E⟩, T ⟩ with and N, C, X, M, E ∈ L satisﬁable in T
Ensure: P ′ = ⟨C ′ , X ′ , M ′ , E ′ ⟩ with C ′ , X ′ , M ′ , E ′ ∈ L satisﬁable in T
 1: J1 := C ⊓ X ⊓ M ⊓ E
 2: J2 := C ⊓ X ⊓ M
 3: ⟨GN , KN ⟩ := contract(N, J1 , T )                                                 // [8]
 4: HN := abduce(KN , J1 , T )                                                         // [8]
 5: C ′ := dif f erence(KN , HN , T )                                                 // [14]
 6: X ′ := GN
 7: M ′ := HN
 8: E ′ := computeBonus(KN , J2 , T )                                                  // [8]
 9: return P ′ = ⟨C ′ , X ′ , M ′ , E ′ ⟩


applying CIPs in cascade, which is not compliant with the purpose of the in-
ference. CIP allows to integrate an “older” snapshot with “new” information to
produce an “updated” snapshot, which reﬂects the viewpoint of the agent that
has performed the integration.
    It is important to highlight that ∀P = ⟨C, X, M, E⟩, C ⊓ X ⊓ M ⊓ E is
consistent. Indeed, C and X are two parts of the produced annotation N , which
is always consistent by assumption. M is derived from C and E is the result of
Bonus, which is always consistent with its input.
    The CIP-based protocol has a further interesting property: it reaches a steady
state in just two observation rounds after every variation in information. For-
mally:
Theorem 1. Given a reference TBox T , let A1 , A2 , . . . , An be n agents which
receive, integrate and relay envelopes P1 , P2 , . . . , Pn in cascade, with Ai ̸= Ai+1 ∀i.
Let N1 , N2 , . . . , Nn be the concept expressions –all satisfiable in T – of the infor-
mation they detect respectively. Then ∀i = 1, . . . , n−2 and ∀S satisfiable concept
in T : (Ci ⊑ S) ∧ (Ni+1 ⊑ ¬S) ∧ (Ni+2 ⊑ ¬S) ⇒ Ci+2 ⊑ ¬S.
Proof. If Ci ⊑ S ∧ Ni+1 ⊑ ¬S, then Ci and Ni+1 are inconsistent and lines 3
and 6 of Algorithm 1 ensure that Xi+1 ⊑ ¬S. In the subsequent CIP between
Ni+2 and Pi+1 , ¬S will not be a source of inconsistency and KN,i+2 ⊑ ¬S (line
3). Since ¬S is in both Ni+2 and KN,i+2 , it will not be part of MN,i+2 and line
5 of CIP algorithm ensures that Ci+2 ⊑ ¬S.
    This means a MAS adopting the proposed protocol can (i) follow rapid
changes in environmental conditions closely and (ii) recover from a detection
mistake quickly. Furthermore, the approach is grounded on the OWA, which
makes it well suited for incomplete information, while Theorem 1 allows it to
cope with noisy data. Finally, Algorithm 1 clearly shows that CIP complexity
depends directly on the one of Abduction, Contraction, Bonus and Diﬀerence
inference services. In particular, the experimental evaluations with Mini-ME
worked on the ALN (Attributive Language with unqualiﬁed Number restric-
tions) DL with simple-TBoxes [9], for which structural algorithms exist with
PTIME complexity for all these services, so CIP has PTIME complexity too.
6

4     Experiments and performance evaluation


A prototypical implementation of the proposed framework was developed for
swarm intelligence scenarios with the NTCUns network simulator [15]. The
testbed simulates a VANET (Vehicular Ad-hoc NETwork) for cooperative mon-
itoring of driving risk factors, where each agent runs on a smartphone in a car
and gathers data from phone micro-devices as well as from the OBD-II (On-
Board Diagnostics) port integrated in the vehicle. Raw data are analyzed and
translated in concept expressions referred to an ontology modeling road features,
traﬃc, weather and driving style [13].
    The early performance test reported here1 aimed to evaluate the sustainabil-
ity of the proposed approach in pervasive contexts. In the simulations, agents
move according to the Manhattan mobility model [1] and exchange envelopes
through wireless ad-hoc connections. Reasoning is supported by the Mini-ME
matchmaker [10], extended with Concept Diﬀerence and Integration inference
services. Knowledge capturing is simulated via pre-deﬁned annotations pertain-
ing to diﬀerent zones of a map. The reference ALN ontology includes 99 classes,
18 object properties and 272 axioms. Each annotation contains observations of
either 5 or 6 properties, each expressed through an existential-universal restric-
tion pair; atomic concepts are the ﬁllers of universal restrictions. Two scenarios
were simulated, diﬀering in the number and density of nodes, as well as in en-
vironmental conditions. Tests were executed on an Asus UX31A notebook with
Intel Core i7 3517U processor (dual core, 1.9-3.0 GHz), 4 GB DDR3 1600 MHz
SDRAM, 256 GB SATA III SSD disk and GNU/Linux Fedora 16 operating
system. Each scenario was run 3 times and average values were taken. Table 2
summarizes simulation parameters, while Table 3 reports on results. The greater
node count in Scenario 2 leads to a higher number of envelope exchanges and In-
tegration resolutions. Average times are below 10 msec: even taking into account
an order of magnitude performance penalty on mobile devices or single-board
computers w.r.t. the testbed hardware [10], the CIP inference service appears
eﬃcient enough for swarm intelligence in pervasive computing scenarios.


    Table 2: Simulation parameters
Scenario                   1     2
No. of agents              60    80                   Table 3: Test results
Sense & process period (s) 2     2               Scenario           1    2
Max agent speed (m/s)      36    50              CIP resolutions    9330 16444
Map size (km)              5 × 2 10 × 2          Avg. CIP time (ms) 9.8 8.1
No. of map zones           9     10
Duration (s)               300 300


1
    See http://sisinﬂab.poliba.it/swottools/minime/download/ore2015exp.zip
                                                                                      7

5   Conclusion
A novel extensive semantic-based framework has been proposed for information
fusion in pervasive multi-agent contexts, based on non-standard, non-monotonic
inference services. It allows to reconcile inconsistent observations and makes the
MAS able to reach quickly a steady state with a coherent situation awareness.
Performance evaluation with the optimized Mini-ME mobile matchmaker sug-
gests adequate eﬃciency. Future work includes integration in an oﬀ-the-shelf
message-oriented middleware for swarm intelligence and in VANET scenarios.
Extensive experiments to evaluate the eﬀectiveness of the proposed approach
w.r.t. the state of the art will concern: reasoning performance on very resource-
constrained devices (e.g., sensor motes); scalability w.r.t. the size and complexity
of managed ontology and expressions, the number of agents and monitored pa-
rameters; communication performance of the devised protocol; quality of the
disseminated information with respect to application goals in realistic scenarios.
Finally, theoretical investigation is underway to extend the approach to multi-
item fusion.


Acknowledgments
The work was supported by the Italian PON project PLATINO (PLATform for
INnOvative services in future internet) and the ETCP project ARGES (pAssen-
geRs and loGistics information Exchange System).


References
 1. Bai, F., Sadagopan, N., Helmy, A.: IMPORTANT: A framework to systematically
    analyze the Impact of Mobility on Performance of RouTing protocols for Adhoc
    NeTworks. In: INFOCOM 2003. Twenty-Second Annual Joint Conference of the
    IEEE Computer and Communications. IEEE Societies. vol. 2, pp. 825–835. IEEE
    (2003)
 2. Calvanese, D., De Giacomo, G., Lenzerini, M., Rosati, R.: Logical foundations of
    peer-to-peer data integration. In: Proceedings of the twenty-third ACM SIGMOD-
    SIGACT-SIGART symposium on Principles of database systems. pp. 241–251.
    ACM (2004)
 3. Calvo, T., Beliakov, G.: Aggregation functions based on penalties. Fuzzy sets and
    Systems 161(10), 1420–1436 (2010)
 4. Castanedo, F., Garcı́a, J., Patricio, M.A., Molina, J.M.: Data fusion to improve
    trajectory tracking in a Cooperative Surveillance Multi-Agent Architecture. Infor-
    mation Fusion 11(3), 243–255 (2010)
 5. Hlinka, O., Hlawatsch, F., Djuric, P.M.: Distributed particle ﬁltering in agent net-
    works: A survey, classiﬁcation, and comparison. Signal Processing Magazine, IEEE
    30(1), 61–81 (2013)
 6. Kennedy, J., Kennedy, J.F., Eberhart, R.C.: Swarm intelligence. Morgan Kauf-
    mann (2001)
 7. Konieczny, S., Pérez, R.P.: Logic based merging. Journal of Philosophical Logic
    40(2), 239–270 (2011)
8

 8. Ruta, M., Di Sciascio, E., Scioscia, F.: Concept abduction and contraction in
    semantic-based P2P environments. Web Intelligence and Agent Systems 9(3), 179–
    207 (2011)
 9. Ruta, M., Scioscia, F., Di Sciascio, E., Gramegna, F., Loseto, G.: Mini-me: the
    mini matchmaking engine. In: OWL Reasoner Evaluation Workshop (ORE 2012).
    vol. 858, pp. 52–63 (2012)
10. Ruta, M., Scioscia, F., Loseto, G., Gramegna, F., Ieva, S., Di Sciascio, E.: Mini-
    ME 2.0: powering the Semantic Web of Things. In: 3rd OWL Reasoner Evaluation
    Workshop (ORE 2014). CEUR Workshop Proceedings, vol. 1207, pp. 8–15 (2014)
11. Ruta, M., Sciascio, E.D., Piscitelli, G., Scioscia, F.: A ubiquitous knowledge-based
    system to enable RFID object discovery in smart environments. Paciﬁc Asia Jour-
    nal of the Association for Information Systems 2(3) (2010)
12. Ruta, M., Scioscia, F., Di Sciascio, E.: Enabling the semantic web of things: frame-
    work and architecture. In: 2012 IEEE Sixth International Conference on Semantic
    Computing. pp. 345–347. IEEE (2012)
13. Ruta, M., Scioscia, F., Gramegna, F., Di Sciascio, E.: A mobile knowledge-based
    system for on-board diagnostics and car driving assistance. In: UBICOMM 2010,
    The Fourth International Conference on Mobile Ubiquitous Computing, Systems,
    Services and Technologies. pp. 91–96. IARIA (2010)
14. Teege, G.: Making the Diﬀerence: A Subtraction Operation for Description Logics.
    Proceedings of the Fourth International Conference on the Principles of Knowledge
    Representation and Reasoning (KR94) pp. 540–550 (1994)
15. Wang, S., Chou, C.: NCTUns tool for wireless vehicular communication network
    researches. Simulation Modelling Practice and Theory 17(7), 1211–1226 (2009)