Integrating knowledge compilation with reinforcement learning for routes

• Main Authors: LING, Jiajing, CHANDAK, Kushagra, KUMAR, Akshat
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2021
• Subjects: Databases and Information Systems
• Online Access: https://ink.library.smu.edu.sg/sis_research/6898; https://ink.library.smu.edu.sg/context/sis_research/article/7901/viewcontent/Integrating_Knowledge_Compilation_with_Reinforcement_Learning_for_Routes.pdf
• Institution: Singapore Management University

Sequential multiagent decision-making under partial observability and uncertainty poses several challenges. Although multiagent reinforcement learning (MARL) approaches have increased the scalability, addressing combinatorial domains is still challenging as random exploration by agents is unlikely to generate useful reward signals. We address cooperative multiagent pathfinding under uncertainty and partial observability where agents move from their respective sources to destinations while also satisfying constraints (e.g., visiting landmarks). Our main contributions include: (1) compiling domain knowledge such as underlying graph connectivity and domain constraints into propositional logic based decision diagrams, (2) developing modular techniques to integrate such knowledge with deep MARL algorithms, and (3) developing fast algorithms to query the compiled knowledge for accelerated episode simulation in RL. Empirically, our approach can tractably represent various types of domain constraints, and outperforms previous MARL approaches significantly both in terms of sample complexity and solution quality on a number of instances.