A Bilinear Programming Approach for Multiagent Planning
This work provides a more efficient and general solution for multiagent coordination, which is incremental but offers significant practical improvements in domains like robotics or logistics.
The authors tackled the computationally hard problem of multiagent planning by formulating two-agent problems as bilinear programs and developed a successive approximation algorithm that reduces computation time by about four orders of magnitude compared to the state-of-the-art coverage set algorithm.
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.