Collaborative paradigms are essential in ubiquitous computing. 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 fusion 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.
The increasing effectiveness 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 effort is being spent to enhance flexibility
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 [
This paper introduces a novel semantic-based approach for information fusion
in ubiquitous MAS. It exploits non-standard, non-monotonic reasoning allowing
agents to integrate captured and received knowledge in a coherent view. A new
complex inference service has been defined for this purpose, capable of
managing inconsistencies in information acquired by different agents. The framework
leverages and extends the Mini-ME mobile matchmaker reasoning services [
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
Multi-agent information fusion. Several approaches exist for distributed
information aggregation in agent networks and MAS. When dealing with numerical
data only, aggregation functions [
Semantic-based multi-agent intelligence relies on operators and inference
services for information fusion on formulas. Peer-to-peer information integration in
[
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. Basically, 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 information 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 envelope 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. Furthermore, 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 C (Confirmed) 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 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 field M , while other fields 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 field 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 fields of both input and output envelopes. The logic problem to solve is named Concept Integration and is formalized as: De nition 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 satisable in T . A Concept Integration Problem (CIP), identi ed by ⟨L; N; P; T ⟩, is nding a 4-tuple of concept expressions P ′ = ⟨C′; X′; M ′; E′⟩, which is the integration 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, Difference 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 Difference 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 Algorithm 1 Concept Integration Problem solution applying CIPs in cascade, which is not compliant with the purpose of the inference. CIP allows to integrate an “older” snapshot with “new” information to produce an “updated” snapshot, which reflects 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. Formally: 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 satis able in T { of the information they detect respectively. Then ∀i = 1; : : : ; n − 2 and ∀S satis able 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 Difference
inference services. In particular, the experimental evaluations with Mini-ME
worked on the ALN (Attributive Language with unqualified Number
restrictions) DL with simple-TBoxes [
A prototypical implementation of the proposed framework was developed for
swarm intelligence scenarios with the NTCUns network simulator [
The early performance test reported here1 aimed to evaluate the
sustainability of the proposed approach in pervasive contexts. In the simulations, agents
move according to the Manhattan mobility model [
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 suggests adequate efficiency. Future work includes integration in an off-the-shelf message-oriented middleware for swarm intelligence and in VANET scenarios. Extensive experiments to evaluate the effectiveness of the proposed approach w.r.t. the state of the art will concern: reasoning performance on very resourceconstrained devices (e.g., sensor motes); scalability w.r.t. the size and complexity of managed ontology and expressions, the number of agents and monitored parameters; 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 multiitem fusion.
The work was supported by the Italian PON project PLATINO (PLATform for INnOvative services in future internet) and the ETCP project ARGES (pAssengeRs and loGistics information Exchange System).