Multiagent Planning and Learning As MILP

Jilles Dibangoye (1) , Olivier Buffet (2) , Akshat Kumar (3)

1 CHROMA - Robots coopératifs et adaptés à la présence humaine en environnements dynamiques
2 LARSEN - Lifelong Autonomy and interaction skills for Robots in a Sensing ENvironment
3 SIS - Singapore Management University

The decentralized partially observable Markov decisionprocess offers a unified framework for sequential decision-making by multiple collaborating agents but remains in-tractable. Mixed-integer linear formulations proved use-ful for partially observable domains, unfortunately ex-isting applications restrict to domains with one or twoagents. In this paper, we exploit a linearization propertythat allows us to reformulate nonlinear constraints fromn-agent settings into linear ones. We further present plan-ning and learning approaches relying on MILP formula-tions for general and special cases, including network-distributed and transition-independent problems. Experi-ments on standard2-agent benchmarks as well as domainswith a large number of agents provide strong empiricalsupport to the methodology.

Les processus décisionnels de Markov décentralises et partiellement observables (Dec-POMDPs) offrent un cadre unifie pour la prise de décisions séquentielles par de plusieurs agents collaboratifs—mais ils restent difficiles`a résoudre. Les reformulations en programmes linéaires mixtes (PLMs) se sont avérées utiles pour les processus décisionnels de Markov partiellement observables.Malheureusement, les applications existantes se limitent uniquement aux domaines mobilisant un ou deux agents. Dans cet article, nous exploitons une propriété de linéarisation qui nous permet de reformuler les contraintes non linéaires, omniprésentes dans les systèmes multi-agents, pour en faire des contraintes linéaires. Nous présentons en outre des approches de planification et d’apprentissage s’appuyant sur de nouvelles reformulations en PLMs des Dec-POMDPs, dans le cas général ainsi que quelques cas spécifiques. Les expérimentations sur des bancs de test standards`a deux et plus de deux agents fournissent un solide soutien`a cette méthodologie.

Domaines: Intelligence artificielle [cs.AI]

Jilles Dibangoye, Olivier Buffet, Akshat Kumar. Multiagent Planning and Learning As MILP. JFPDA 2020 - Journées Francophones surla Planification, la Décision et l’Apprentissagepour la conduite de systèmes, Jun 2020, Angers (virtuel), France. pp.1-12. ⟨hal-03081548⟩