Hierarchical Task Networks as Social Laws

Abstract: Agents operating a multi-agent system must typically co- ordinate their actions to avoid interfering with each other. Social laws are an increasingly popular paradigm for multi- agent coordination, which does not require communication between the agents. In single-agent planning, Tail-recursive Totally ordered Hierarchical Task Network (TO-HTN) plan- ning is a well-understood formalism for specifying control knowledge for autonomous agents. We propose an interpre- tation of Tail-recursive TO-HTN as implicit social laws for multi-agent systems, viewing Tail-recursive TO-HTN plan- ning as a useful formalism for restricting the set of plans each agent chooses from. We aim to use existing compilations and translations in order to interpret TO-HTN as explainable So- cial Law constraints, thus we lay the groundwork for a fully mature synthesis framework of such mechanisms in future works. We formalize this idea through the Multi-Agent HTN (MA-HTN) framework that we define, and adapt definitions of robustness from earlier work on social laws in the classical planning setting. To verify robustness, we combine the re- cent HTN-to-classical compilation with existing multi-agent robustness-checking methods for MA-STRIPS, enabling clas- sical planners to perform robustness verification. Our results position TO-HTNs as structured, interpretable coordination constraints and lays the groundwork for automated synthesis of robust hierarchical social laws.