Dhaka University Journal of Applied Science & Engineering

• Md Mosaddek Khan
  Department of Computer Science and Engineering, University of Dhaka, Dhaka, Bangladesh
• N V Q Trung
  School of Electronics and Computer Science, University of Southampton, Southampton, United Kingdom

The Max-Product belief propagation algorithm has been widely used to process constraints associated with optimization problems in a broad range of application domains such as information theory, multi-agent systems, image processing, etc. The constraint optimization of a given problem is typically accomplished by performing inference with the use of a message passing process. During the process, the Max-Product algorithm performs repetitive maximization operation, which has been considered as one of the main reasons the algorithm can be computationally expensive. In more detail, scalability becomes a challenge when Max-Product has to deal with constraint functions with high arity and/or variables with a large domain size. In either case, the ensuing exponential growth of search space can make the maximization operator of the algorithm computationally infeasible in practice. In effect, it is frequently observed that the output of an algorithm becomes obsolete or unusable as the optimization process takes too long. Specifically, the issue of an algorithm taking too long to complete its internal inference process becomes more severe and prevalent as the size of the problem increases. As a result, the practical scalability of such algorithms is constrained. However, it is challenging to maintain the solution quality while reducing the computation cost of the algorithm. This is important because success in doing so will eventually reduce the algorithm’s overall completion time without compromising on the quality of its solution. To address this issue, we develop a generic pruning technique that enables the maximization operator of the Max-Product algorithm to operate on a significantly reduced search space of at least around 85% or more (i.e. empirical observation). Additionally, we demonstrate theoretically that the pruned search space obtained through our approach has no negative impact on the algorithm’s outcome. Finally, further empirical evidence notably suggests that our proposed approach brings down 50% to around 99% of the time required to complete a single maximization operation.

1. J. Pearl, Probabilistic reasoning in intelligent systems: Networks of plausible inference (representation and reasoning), 1988
2. J. Sun, N.-N. Zheng, H.-Y. Shum, Stereo matching using belief propagation, IEEE Transactions on pattern analysis and machine intelligence, 25 (7), 787–800, 2003
3. M. P. Fossorier, M. Mihaljevic, H. Imai, Reducecomplexity iterative decoding of low-density parity check codes based on belief propagation, IEEE Transactions on communications, 47 (5), 673–680, 1999
4. A. Farinelli, A. Rogers, A. Petcu, N. R. Jennings, Decentralised coordination of low-power embedded devices using the max-sum algorithm, in: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), Vol. 2, pp. 639–646, 2008
5. R. Dechter, Reasoning with graphical models (2007)
6. F. R. Kschischang, B. J. Frey, H. Loeliger, Factor graphs and the sum-product algorithm, IEEE Transactions on Information Theory, 47 (2), 498–519, 2001
7. A. R. Leite, F. Enembreck, J. A. Barth`es, Distributed constraint optimization problems: review and perspectives, Expert Systems with Applications, 41 (11), 5139–5157, 2014
8. F. Fioretto, E. Pontelli, W. Yeoh, Distributed constraint optimization problems and applications: A survey, Journal of Artificial Intelligence Research, 61, 623–698, 2018
9. K. P. Murphy, Y. Weiss, M. I. Jordan, Loopy belief propagation for approximate inference: An empirical study, in: Proceedings of the Fifteenth conference on Uncertainty in artificial intelligence, Morgan Kaufmann Publishers Inc., pp.467–475, 1999
10. P. F. Felzenszwalb, D. P. Huttenlocher,Efficient belief propagation for early vision, International journal of computer vision, 70 (1), 41–54, 2006
11. A. Farinelli, A. Rogers, N. R. Jennings, Agent-based decentralised coordination for sensor networks using the max-sum algorithm, Autonomous agents and multi-agent systems, 28 (3), 337–380, 2014
12. S. M. Aji, R. McEliece, The generalized distributive law, IEEE Transactions on Information Theory, 46 (2), 325–343, 2000
13. M. M. Khan, L. Tran-Thanh, S. D. Ramchurn, N. R. Jennings, Speeding up gdl-based message passing algorithms for large-scale dcops, The Computer Journal, 61 (11), 1639 –1666, 2018.
14. Y. Kim, V. Lesser, Improved max-sum algorithm for dcop with n-ary constraints, in: Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 191–198, 2013.
15. S. D. Ramchurn, A. Farinelli, K. S. Macarthur, N. R. Jennings, Decentralized coordination in robocup rescue, Computer Journal, 53, 1447–1461, 2010
16. K. S. Macarthur, R. Stranders, S. D. Ramchurn, N. R. Jennings, A distributed anytime algorithm for dynamic task allocation in multi-agent systems, in: Proceedings of the 25th AAAI Conference on Artificial Intelligence, pp. 701–706, 2011
17. R. Stranders, A. Farinelli, A. Rogers, N. R. Jennings, Decentralised coordination of mobile sensors using the max-sum algorithm, in: Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI), Vol. 9, pp. 299–304, 2009
18. M. M. Khan, L. Tran-Thanh, N. R. Jennings, A generic domain pruning technique for gdl-based dcop algorithms in cooperative multi-agent systems, in: Proceedings of the 17th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), IFAAMAS, Stockholm, Sweden, pp. 1595–1603, 2018
19. Z. Chen, X. Jiang, Y. Deng, D. Chen, Z. He, A generic approach to accelerating belief propagation based incomplete algorithms for dcops via a branch-and-bound technique, in: Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33, pp. 6038–6045, 2019