Comment & Analysis
In any industrial or real-world domain, robots operate under uncertainty. For instance, an inspection robot’s sensors may be noisy, making it difficult to ascertain the quality of a manufactured product. Decision-making in such settings is done using each robot’s history of previously taken actions and observations of the environment, which informs its next action.
However, the state-to-state transitions for robots are often uncertain. If we tell a robot to move 0.5m north in a real-world domain, it may succeed 95% of the time, but may fail the remaining 5% because of noisy observations, moving obstacles, or other sources of uncertainty. Other than observations, the behaviour of a robot is determined by typically random variables, which means that a probabilistic decision-making framework is required to solve a robot’s optimal action at a given time.
One framework for solving decision-making problems for a team of robots operating under uncertainty is the ‘decentralised partially observable Markov decision process’ (Dec-POMDP). This framework is decentralised since it requires no explicit communication or sense of consensus on the overall team’s state among the robots during operation.
Communication between robots is a strong assumption. If robots communicate their actions and observations with each other at every time-step, the problem becomes centralised and easier to solve. The Dec-POMDP, however, is designed to handle lack of communication, which is a valid concern for real-world, multi-robot domains. The solution to the Dec-POMDP is a joint policy dictating the action that each robot should take, based on its own history of actions and noisy observations. During the online execution phase, no consensus on the overall team’s state is required. Each robot simply follows the agreed-upon policy.
The challenge in Dec-POMDPs is that they are difficult to solve, making them unrealistic for real-world scenarios. However, the notion of macro-actions (MAs) has recently been introduced into the scope of decision-making processes. MAs are temporally extended actions that can be used to represent highly complex chains of more primitive actions. For instance, ‘go-to-home-position’ or ‘open-the-door’ are MAs, whereas ‘move 0.5m north’ would be a low-level/primitive action. Adding MAs into the process transforms the Dec-POMDP problem to a ‘high-level’ scope, where the robots no longer make decisions in the ‘low-level action space’.
In the past, MAs have typically been designed manually by a domain expert – a person familiar with the low-level capabilities of the robots, who constructs chains of actions to achieve high-level tasks. But our recent work allows automatic construction of MAs, and requires minimal domain knowledge. Our framework is called the Dec-POSMDP, the extra S indicating that the domain is now semi-Markovian. Our motivation is to modify Dec-POMDPs for real-world applications, leveraging their ability to handle uncertainty.
We have tested our framework on a small group of quadrotors, in a constrained version of the autonomous package delivery problem envisioned by Amazon and Google. By adding the no-communication constraint to the autonomous package delivery domain, we show that our framework can be used to solve complex variants of more traditional planning and task-allocation domains.
Our work was funded by Boeing, and there is industry interest in applying autonomous vehicles to complex real-world domains, especially in aerospace. We encourage other researchers and members of industry to use our framework to solve such problems.