A multi-agent approach for solving optimization problems involving expensive resources

ABSTRACT

In this paper, we propose a multi-agent approach for solving a class of optimization problems involving expensive resources, where monolithic local search schemes perform miserably. More specifically, we study the class of bin-packing problems. Under our proposed Fine-Grained Agent System scheme, rational agents work both collaboratively and selfishly based on local search and mimic physics-motivated systems. We apply our approach to a generalization of bin-packing - the Inventory Routing Problem with Time Windows - which is an important logistics problem, and demonstrate the efficiency and effectiveness of our approach.

REFERENCES

• 1: Makoto Yokoo , Edmund H. Durfee , Toru Ishida , Kazuhiro Kuwabara, The Distributed Constraint Satisfaction Problem: Formalization and Algorithms, IEEE Transactions on Knowledge and Data Engineering, v.10 n.5, p.673-685, September 1998 [doi>10.1109/69.729707]
• 2: Pragnesh Jay Modi , Wei-Min Shen , Milind Tambe , Makoto Yokoo, An asynchronous complete method for distributed constraint optimization, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860602]
• 3: Armstrong, A. and E. Durfee, 1997 Dynamic Prioritization of Complex Agents in Distributed Constraint Satisfaction Problems. Proc. 15th International Joint Conference on Artificial Intelligence, 620--625
• 4: Hyuckchul Jung , Milind Tambe, Performance models for large scale multiagent systems: using distributed POMDP building blocks, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860623]
• 5: Kwok Ching Tsui , Jiming Liu, Multiagent diffusion and distributed optimization, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860603]
• 6: Onn Shehory , Sarit Kraus , Osher Yadgar, Emergent cooperative goal-satisfaction in large-scale automated-agent systems, Artificial Intelligence, v.110 n.1, p.1-55, May 1999 [doi>10.1016/S0004-3702(99)00019-3]
• 7: Hoong Chuin Lau , Qizhang Liu , Hirotaka Ono, Integrating local search and network flow to solve the inventory routing problem, Eighteenth national conference on Artificial intelligence, p.9-14, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 8: De Backer B., and Furnon V., 1997 Meta-heuristics in Constraint Programming Experiments with Tabu Search on the Vehicle Routing Problem, Proc. 2nd Metaheuristics International Conference
• 9: Hoong Chuin Lau , Andrew Lim , Qi Zhang Liu, Solving a Supply Chain Optimization Problem Collaboratively, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.780-785, July 30-August 03, 2000
• 10: Lau H. C., Lim M. K., Wan W. C., Wang H. and Wu X., 2003 Solving Multi-Objective Multi-Constrained Optimization Problems using Hybrid Ants System and Tabu Search. Proc. 5th Metaheuristics International Conference
• 11: 0. Shehory, Coalition Formation for Large-Scale Electronic Markets, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.167, July 10-12, 2000

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

Keywords:
expensive resources, multi-agent system, optimization problems