A Bilinear Programming Approach for Multiagent Planning

DOI10.1613/JAIR.2673MaRDI QIDQ3651464zbMATH OpenOpenAlexWikidataFDO

Authors Marek Petrik, Shlomo Zilberstein

Publication date 10 December 2009

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.3461

zbMATH Keywords

bilinear programssuccessive approximation algorithmtwo-agent problems

Mathematics Subject Classification ID

Agent technology and artificial intelligence (68T42) Approximation algorithms (68W25)

Abstract: Multiagent planning and coordination problems are common and known to be computationally hard. We show that a wide range of two-agent problems can be formulated as bilinear programs. We present a successive approximation algorithm that significantly outperforms the coverage set algorithm, which is the state-of-the-art method for this class of multiagent problems. Because the algorithm is formulated for bilinear programs, it is more general and simpler to implement. The new algorithm can be terminated at any time and-unlike the coverage set algorithm-it facilitates the derivation of a useful online performance bound. It is also much more efficient, on average reducing the computation time of the optimal solution by about four orders of magnitude. Finally, we introduce an automatic dimensionality reduction method that improves the effectiveness of the algorithm, extending its applicability to new domains and providing a new way to analyze a subclass of bilinear programs.

Recommendations

• The multiagent planning problem
• Efficient and distributable method for solving the multiagent plan coordination problem
• A single-agent approach to multiagent planning
• scientific article; zbMATH DE number 1080096
• A heuristic technique for multi-agent planning
• scientific article; zbMATH DE number 2222691
• scientific article; zbMATH DE number 2243394
• scientific article; zbMATH DE number 1929179
• scientific article; zbMATH DE number 1931658

Cited in

(5)

• Computing convex coverage sets for multi-objective coordination graphs
• Algorithms for recursive delegation
• Online planning for multi-agent systems with bounded communication
• A sufficient statistic for influence in structured multiagent environments
• A mixed-integer linear programming reduction of disjoint bilinear programs via symbolic variable elimination

This page was built for publication: A Bilinear Programming Approach for Multiagent Planning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3651464)