Multi-Agent Path Planning Under Observation Schedule Constraints

We consider the problem of enhanced security of multi-robot systems to prevent cyber-attackers from taking control of one or more robots in the group. We build upon a recently proposed solution that utilizes the physical measurement capabilities of the robots to perform introspection, i. e. , detect the malicious actions of compromised agents using other members of the group. In particular, the proposed solution finds multi-agent paths on discrete spaces combined with a set of mutual observations at specific locations to detect robots with significant deviations from the preordained routes. In this paper, we develop a planner that works on continuous configuration spaces while also taking into account similar spatio-temporal constraints. In addition, the planner allows for more general tasks that can be formulated as arbitrary smooth cost functions to be specified. The combination of constraints and objectives considered in this paper are not easily handled by popular path planning algorithms (e. g. , sampling-based methods), thus we propose a method based on the Alternating Direction Method of Multipliers (ADMM). ADMM is capable of finding locally optimal solutions to problems involving different kinds of objectives and non-convex temporal and spatial constraints, and allows for infeasible initialization. We benchmark our proposed method on multi-agent map exploration with minimum-uncertainty cost function, obstacles, and observation schedule constraints.

Authors

• Ziqi Yang
• Roberto Tron

Keywords

• Schedules
• Cost function
• Particle measurements
• Path planning
• Convex functions
• Security
• Task analysis
• Inequality Constraints
• Multi-agent Systems
• Combination Of Constraints
• Robot Capabilities
• Simulation Results
• Time Window
• Optimization Problem
• Objective Function
• Feasible Solution
• Kalman Filter
• Hyperplane
• Vector Field
• Functional Applications
• Fisher Information
• Penalty Parameter
• Obstacle Avoidance
• Types Of Constraints
• Update Step
• Velocity Constraints
• Minimum Uncertainty
• End Location
• Non-convex Constraints
• Convex Polygon
• Start Location
• Projection Operator
• Covariance Matrix
• trajectory optimization
• map exploration
• ADMM