Verification of agent navigation in partially-known environments

摘要

This paper establishes a framework based on logic and automata theory in which to model and automatically verify systems of multiple mobile agents moving in environments with partially-known topologies, i.e., ones which are not completely known at design time. Examples include physical agents designed to be used in many spatial environments and not tailored for a specific one, robots in environments not reachable by humans, and software exploring partially-mapped networks. We model spatial environments as graphs whose edges are labelled with directions. We model agents as finite-state machines that move on the graphs by issuing commands of the form “go in direction X”, that can communicate their internal state to other agents, and that can sense agent positions (including current and visited positions). We treat the incomplete information about the spatial environment by studying the decision problem that asks whether a given collection of agents achieve their tasks on all graphs from a class of graphs — this is called the parameterised verification problem. The framework also introduces a new logical language based on Linear Temporal Logic that is tailored for expressing agent navigation tasks in such environments.