Optimal Scheduling of Agents in ADTrees: Specialized Algorithm and Declarative Models
Jaime Arias, Carlos Alberto Olarte, Laure Petrucci, Łukasz Maśko, Wojciech Penczek, Teofil Sidoruk · IEEE Transactions on Reliability · 2024
Expressing attack-defence trees in a multiagent setting allows for studying a new aspect of security scenarios, namely, how the number of agents and their task assignment impact the performance,e.g.,attack time, of strategies executed by opposing coalitions. Optimal scheduling of agents' actions, a nontrivial problem, is thus vital. We discuss associated caveats and propose an algorithm that synthesizes such an assignment, targeting minimal attack time and using the minimal number of agents for a given attack-defence tree. We also investigate an alternative approach for the same problem using rewriting logic, starting with a simple and elegant declarative model, whose correctness (in terms of schedule's optimality) is self-evident. We then refine this specification, inspired by the design of our specialized algorithm, to obtain an efficient system that can be used as a playground to explore various aspects of attack-defence trees. We compare the two approaches on different benchmarks.