From Knowledge- to Belief-Based Programming for Mobile Ad-Hoc Networks
Mobile ad-hoc networks (MANETs) pledge flexible deployments of failure-resistant applications in a variety of scenarios without central infrastructure ranging from disaster recovery to in-classroom networks. These advantages, however, come at the expense of an increased complexity for applications and underlying network protocols. As a consequence thereof, a multitude of middleware solutions have been proposed which aim at simplifying decentralized application development. Knowledge-based programming is the idea to use knowledge an agent posses about a system — for example, a network — to program its behavior based on decision rules. Starting from the idea to utilize this programming abstraction for mobile ad-hoc networks via a general MANET middleware we investigate three major problems for traditional knowledge-based programs in the context of dynamic open multi-agent systems, like MANETs, using the example of disaster recovery robots. We show how to solve those problems by extending knowledge-based programs to open multi-agent systems and giving well-defined semantics for syntactically valid knowledge-based programs based on a nomological notion of knowledge. We finally weaken the idea of knowledge-based programming by dropping the truth requirement, i.e., that knowable implies truth. This yields a notion of belief-based programming. In contrast to knowledge beliefs may be incorrect, however, they must not be arbitrary. To this end, we present several adequacy requirements a sensible belief-based system should satisfy.