On the Power and Limitations of Deception in Multi-Robot Adversarial Patrolling

Noga Talmor, Noa AgmonIJCAI 2017 · DOI

TL;DR

This paper introduces novel deception strategies for multi-robot adversarial patrolling, aiming to make adversaries believe there are more robots than there actually are. By manipulating the adversary's knowledge, defenders can increase their chances of detecting intrusions without necessarily increasing their robot count.

What Problem Does This Paper Address?

The core problem is multi-robot adversarial patrolling, where a group of robots defends a perimeter against a rational adversary trying to penetrate. Existing research often assumes the adversary has full or partial knowledge of the robots' positions, capabilities, and strategies. This paper tackles the challenge of how defenders can leverage the adversary's imperfect knowledge to their advantage. Specifically, it explores how to deceive the adversary into believing the defending force is stronger or more capable than it truly is, thereby deterring penetration attempts.

Methods

The paper proposes two main deception models:

  • Window Deception: This model assumes the adversary can only observe a portion of the perimeter (the "window"). Defenders can then simulate a stronger patrol within this window, making the adversary believe this enhanced presence extends to the entire perimeter. This can be achieved through:
  • Deterministic Patrol with Changing Velocity: Robots can temporarily increase their speed to cover more ground and maintain the illusion of more robots within the window.
  • Random Patrol: By employing randomized movement patterns, defenders can create a patrol that appears consistent with a larger force, even without altering robot capabilities. This involves carefully managing robot movements to avoid revealing anomalies.
  • Scarecrow Deception: This approach involves using "scarecrow" robots that look like real patrolling robots to the adversary but lack actual detection capabilities. These robots are cheaper and easier to maintain. The key is to strategically place these scarecrows alongside real robots to create the illusion of a larger, more capable patrol force. The paper analyzes optimal placement strategies for scarecrows in both perfect and randomized patrol scenarios.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and simulation, with an empirical evaluation mentioned but not detailed in terms of specific datasets.

Key Insights and Ideas

  • Deception as a Resource: The paper frames deception not just as a tactic but as a resource that can be strategically employed to augment a defender's capabilities without increasing physical assets.
  • Exploiting Imperfect Information: The core insight is that an adversary's incomplete view of the operational environment (the "window" or the presence of non-sensing "scarecrows") is a vulnerability that can be exploited.
  • Trade-offs in Deception: The paper highlights the inherent trade-offs between the effectiveness of deception and the probability of detecting actual intrusions. Achieving perfect deception might sometimes come at the cost of reduced detection rates in certain areas.
  • Scarecrows as Cost-Effective Augmentation: Scarecrow robots offer a practical way to increase the perceived strength of a patrol force, especially in scenarios where real robots are expensive or limited.
  • Randomness as a Deception Tool: For random patrols, the paper shows that carefully managed randomness can maintain deception, whereas deterministic patrols require more complex adjustments (like changing robot velocity).

Key Results

  • Window Deception Limitations: It's impossible to perfectly simulate a larger number of robots indefinitely in a deterministic patrol without altering robot capabilities (e.g., changing velocity).
  • Window Deception Possibilities: With changing velocities, it's possible to simulate a larger number of robots, with the achievable number increasing with higher maximum velocities. For random patrols, deception can be maintained indefinitely under certain conditions by carefully managing robot movements and using "readiness areas" for fence robots.
  • Scarecrow Deception Effectiveness: Scarecrows can be optimally placed to maximize the expected probability of penetration detection. The paper provides theorems for calculating these expected probabilities in both perfect and randomized patrol scenarios.
  • Monotonic Increase in Detection: For a fixed total perceived force (Ω), the expected probability of detection increases monotonically with the number of real robots.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that guaranteeing undiscovered deception without changing robot characteristics can only be made for random patrols.
  • The proofs for some theorems are omitted due to space constraints, suggesting a need for more detailed mathematical exposition.
  • The empirical evaluation is mentioned but not detailed, leaving the practical performance of the implemented models open to further investigation.
  • Future Work:
    • Combining the two presented deception models (Window and Scarecrow).
  • Analyzing the influence of deception on penetration detection rates in the "fence" (unobserved) areas.
  • Developing new deception models, such as different window outlines or "honeypots."

Summary updated

BibTeX
@inproceedings{talmor2017power,
  author = {Noga Talmor and Noa Agmon},
  title = {{On the Power and Limitations of Deception in Multi-Robot Adversarial Patrolling}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/61},
}
Figure