Risk-Neutral Multi-Robot Planning for Target Tracking

Team members: Zirui Xu, Naman Gupta, and Akwasi Obeng

Background

In [1], a resilient submodular maximization algorithm is proposed for multi-robot target tracking. That algorithm is resilient to worst-case attacks yet too conservative when the attack is not the worst case. To improve the robot team's utility (i.e., the number of tracked targets) of the latter case, we incorporate each robot's risk of being attacked into the sequential decision-making. In this mini-project, we implement a risk-neutral greedy algorithm and investigate its efficacy, which might be a little bit beyond the requirement of the project but is similar to one of the baseline algorithm (the sequential greedy algorithm) in the paper.

Proposed Method & Implementation

Specifically, the probability of failure of robot i is formulated as a random variable with Bernoulli distribution, where Prob{fail} = p_i, and Prob{safe} = 1 - p_i, and p_i = (# of targets tracked by the best trajectory candidate of robot i) / (sum of # of targets tracked by the best trajectory candidates of all robots). This definition intuitively indicates that the probability of failure is larger for a robot whose best trajectory candidate is better than others', which makes sense because adversaries are more likely to attack those robots with larger impact. Then, the multiplication of the number of tracked targets and Prob{safe}, i.e., the expectation of the number of tracked targets, is used as the utility of each trajectory for greedily solving the submodular maximization problem. Since we adopt the expection as the risk measure, we term the proposed method as "risk-neutral". The efficacy of the proposed method is evaluated through simulations in MATLAB, and the results are as follows:

(a) Comparison under optimal attack

(b) Comparison under greedy attack

Simulation Results & Implementation Details

In the simulations, a team of 6 drones are deployed to track 30 - 60 ground targets under three different attack models (optimal, greedy, and random), respectively. Each figure shows the utility (average and deviation over 30 trials) of five tracking strategies (brute-force, resilient, risk-neutral, greedy, and random). In each trial, 3 drones malfunction due to denial-of-service attacks, yet the selection of removed drones differs according to the corresponding attack model.

The results show that, the risk-neutral algorithm has a similar utility as the greedy algorithm under optimal and greedy attacks, and has a similar utility as the greedy algorithm and the resilient algorithm under random attacks. Thus, the performance of the risk-neutral algorithm is not significantly different from that of the greedy algorithm in general, which means associating only the risk of being attacked with the utility of trajectories does not matter much to the efficacy. In the rest of the research project, we will be investigating more complex methods to develop resilient target tracking algorithms which are not too conservative.

The implementation takes advantages of the public codes of [1], and our codes is also available online [2].