A comparison of multi-agent state-space exploration approaches for the verification of mixed and partially observable domains

Validation problems concern practically any domain theory that describes the types and properties of objects, classes of states and relations, and the laws of functioning and interaction between objects. Recognition and verification of the state space associated to a determined system is key to solving management problems. Such tasks in the context of state-based systems often require a reachability analysis that displays an exponential expansion of the search space in certain domain theories. Coordinated and decentralized multi-agent exploration can offer efficient solutions to the problem, but the task becomes intractable within certain probabilistic domains. Concretely, the associated 'curse of dimensionality' of partially observable domains, in practice, is a considerable limitation that allows to tackle the recognition task only in terms of suboptimal solutions. However, the signals associated to properties in an environment can be read by different kinds of sensors, which in turn can significantly influence the state exploration time in the recognition task. In this paper, we study multi-agent systems for state-space exploration in environments with partial and mixed observability, and we outline certain conditions under which interchangeability between approaches can be obtained according to efficiency goals. We performed a cost comparison of two multi-agent approaches consisting of automated agents without inner states, with the difference that one of them uses exact, noise immune sensors and the other utilizes unbiased sensors with a certain degree of imprecision. By representing the interpretation of a domain as a path exploration task, we obtained an equation comprising the necessary conditions for an equivalence between the approaches. © 2019 CEUR-WS. All rights reserved.