Simultaneous Task Allocation and Planning Under Uncertainty

We propose novel techniques for task allocation and planning in multi-robot systems operating in uncertain environments. Task allocation is performed simultaneously with planning, which provides more detailed information about individual robot behaviour, but also exploits independence between tasks to do so efficiently. We use Markov decision processes to model robot behaviour and linear temporal logic to specify tasks and safety constraints. Building upon techniques and tools from formal verification, we show how to generate a sequence of multi-robot policies, iteratively refining them to reallocate tasks if individual robots fail, and providing probabilistic guarantees on the performance (and safe operation) of the team of robots under the resulting policy. We implement our approach and evaluate it on a benchmark multi-robot example.

Authors

• Fatma Faruq
• David Parker 0001
• Bruno Lacerda
• Nick Hawes

Keywords

• Task analysis
• Planning
• Robot kinematics
• Resource management
• Uncertainty
• Probabilistic logic
• Task Allocation
• Multi-agent Systems
• Team Performance
• Markov Decision Process
• Uncertain Environment
• Swarm Robotics
• Formal Verification
• Safety Constraints
• Linear Logic
• Individual Robots
• Sequential Model
• Optimal Policy
• Pathfinding
• Point Of Failure
• Transition Function
• Failure Conditions
• Planning Approach
• Starting State
• Allocation Process
• Value Iteration
• Markov Decision Process Model
• Switching Transition
• Single Robot
• Robot State
• Set Of Formulas
• Service Robots
• Robot Model
• Model Checking
• Planning Problem
• Probability In Order