Highlight of a paper series on epistemic reasoning for multirobot systems
Recently, I’ve been reading a series of papers by Lauren Bramblett, Nicola Bezzo, and their collaborators, on improving multirobot systems using epistemic reasoning - that is, reasoning about other robots’ knowledge and beliefs. This line of work is quite far from my research area; however, given the papers’ references to epistemic logic and my interest in logic in general and background in embedded systems, it appeared to be an interesting read. I was not disappointed, quite the contrary - the papers surprised me.
Context
Imagine having a fleet of unmanned vehicles (say, drones or ground vehicles) and wanting to use them to (1) cover a large, partially unknown geographical area, (2) search for things to do in the area (“tasks”) and (3) do these. In the beginning, one might have a centrally-computed plan saying which vehicles go where; however, the vehicles may run into issues executing the plan and may have to adapt the original plan. In such case, if communication becomes unavailable, the local change in one vehicle’s plan may break assumptions or expectations of the other vehicles, endangering or slowing down the fleet’s mission.
In more concrete terms, the mission of the fleet might be, for example:
- localizing places in a forest where a fire might be starting, possibly stopping the fire;
- localizing and rescuing wounded soldiers on a battlefield;
- finding lost tourists in mountains, possibly leading them to safety
The area would be known only partially, due to factors like
- fallen trees blocking roads in the forest;
- buildings or bridges that were destroyed because of a war;
- unexpected terrain differences because of heavy rain (water, mud, …).
And the communication might be unavailable due to weather, intentional electromagnetic interference, or large distance between the vehicles.
In that line of work, the authors address the question: “Can the robots use the notion of belief about other robots, and beliefs about beliefs of other robots, to compensate for the unavailability of communication”? To that end, they propose to use dynamic epistemic logic to reason about (possibly higher-order) beliefs of robots. But not in the way I expected.
The surprise
When I first run into this line of work, I though that the robots would hold some beliefs represented as logical formulas, that these formulas would get transformed in the lucky situation when communication with other robots works, and that this collection of beliefs would be queried, in the PROLOG-style, time from time, to yield useful information. But I was wrong, this is not how the papers work with beliefs at all!
Instead, each robots holds the collection of worlds they consider possible, explicitly. Each such world contains information about the state about the other robots; the state includes basic information such as position and velocity, but also the map of environment as the robot understands it, and also beliefs of other robots about all robots. That is quite a lot of information to keep and update! Indeed, in the experiments, the number of robots is kept quite low (~5) to keep the computational cost tractable.
And how are these beliefs about other robots and other robots’ beliefs used? For example, in the earliest paper of the series, Epistemic Prediction and Planning with Implicit Coordination for Multi-Robot Teams in Communication Restricted Environments, they are used to dynamically agree on meeting points where the robots gets close enough to communicate. In that paper, when robots lose communication, they go about their way for some time, but when the time runs out, they want to meet; the meeting point is derived based on the robots’ beliefs about their own and other robots’ positions. However, it might happen that one of the robots run into a bad terrain, is going slower than expected, and thus can not arrive at the location at the expected time. Since the robots want to meet, they do not track one state only in which they would believe the other robot is, but multiple (e.g., 3-4) states they consider possible (but less plausible than the state they “believe in”). If the unlucky robot is not present at the expected time at the expected location, the other robots change their belief about which of the tracked states is the most plausible, and recalculate the location where they all expect to meet.
Since no logic formulas are used inside the robots, one might wonder why the paper discusses the syntax of the logic and shows any formulas at all. My guess is that the epistemic logic is used primarily to make sense of (1) what is happening inside the robots, and (2) what various states of robots mean, and to convey the intuition behind the algorithm in terms of understood concepts such as “knowledge” “belief”. That said, since the amount of data the robots how to carry around and compute with is quite large, I wonder if a more symbolic representation of the robots’ beliefs in terms of epistemic logic formulas could be used to scale the approach to larger number of robots.