A Multiagent System-Based Solution for Shipment Operations with Priorities in a Container Terminal
Resumo
This paper proposes the use of a multiagent system-based solution for a proposed robotic-based automation system for the shipment operations of containers with shipment priorities in the port terminal located in Rio Grande City, Brazil. We faced with a problem of optimal policy formulation for teams of resource-limited robotic loaders in stochastic environments, which is composed of two strongly-coupled sub problems: a resource allocation problem and a policy optimization problem. The containers are required to be shared between the loaders, considering the following constraints: the containers have different weights and shipment priorities, the loaders have a maximum load that they can support during a journey, and, due to several reasons (e.g: administrative rules, maintenance schedule), the loaders are made available to the shipping operation only sequentially. We show how to combine the two problems, by formulating a policy optimization problem over the loading/unloading operations for each loader, as it becomes available. To solve the problem of container allocation to the next available loader we use a reduction of the Knapsack Problem. Then, we use Markov Decision Processes to decide on the shipment operations preformed by that loader in the terminal yard. These two processes are connected, since the container allocation process determines the states of the Markov chain that each loader actually visits. We simulated the resulting shipment operations using Net Logo.
Referências
Boutilier, C., Brafman, R., and Geib, C. (1997). Prioritized goal decomposition of Markov Decision Processes: Towards a synthesis of classical and decision theoretic planning. In Pollack, M., editor, Proc. 15th Intl. Joint Conf. on Artificial Intelligence, pages 1156–1163, San Francisco. Morgan Kaufmann.
Dean, T., , and Lin, S.-H. (1995). Decomposition techniques for planning in stochastic domains. In Proc. Intl. Joint Conf. on Artificial Intelligence.
Dimuro, G. P., Costa, A. C. R., and Gonçalves, L. V. (2008). Recognizing and learning observable social exchanges strategies in open societies. In Proc. 1st Braz. Work. on Social Simulation - BWSS 2008/XIX Braz. Symp. on Artificial Intelligence - SBIA 2008, Salvador, pages 140 –152, Porto Alegre. SBC.
Dolgov, D. A. and Durfee, E. H. (2004). Optimal resource allocation and policy formulation in loosely-coupled Markov Decision Processes. In Zilberstein, S., Koehler, J., and Koenig, S., editors, Proc. 14th Intl. Conf. on Automated Planning and Scheduling (ICAPS 2004), pages 315–324, Whistler. AAAI.
Guo, M. and Conitzer, V. (2010). Optimal-in-expectation redistribution mechanisms. Artificial Intelligence, 174(5-6):363 – 381.
Huang, Z., van der Aalst,W., Lu, X., and Duan, H. (2011). Reinforcement learning based resource allocation in business process management. Data & Knowledge Engineering, 70(1):127 – 145.
Kaebling, L. P., Littman, M. L., and Cassandra, A. R. (1998). Planning and acting in partially observable stochastic domains. Artificial Intelligence, 101(1–2):99–134.
Meuleau, N., Hauskrecht, M., Kim, K., Peshkin, L., Kaelbling, L. P., Dean, T., and Boutilier, C. (1998). Solving very large weakly coupled Markov Decision Processes. In Proc. 15th Nat. Conf. on Artificial Intelligence (AAAI-98), 10th Conf. on Innovative Applic. of Artificial Intelligence (IAAI-98), pages 165–172, Menlo Park. AAAI Press.
Parr, R. (1998). Flexible decomposition algorithms for weakly coupled Markov Decision Problems. In Cooper, G. F. and Moral, S., editors, Proc. 14th Conf. on Uncertainty in Artificial Intelligence (UAI-98), pages 422–430, San Francisco. Morgan Kaufmann.
Pereira, D., Gonçalves, L. V., Dimuro, G. P., and da Rocha Costa, A. C. (2008). Towards the self-regulation of personality-based social exchange processes in multiagent systems. In Zaverucha, G. and Costa, A. L., editors, Advances in Artificial Intelligence, volume 5249 of LNAI, pages 113–123. Springer, Berlin.
Ribeiro, C. (2002). Reinforcement learning agents. Artificial Intelligence Review, 17(3):223–250. Russel, S. and Norvig, P. (2003). Artificial Intelligence: A Modern Approach. Prentice Hall, Englewood Cliffs, 3 edition.
Singh, S. and Cohn, D. (1998). How to dynamically merge Markov Decision Processes. In Jordan, M. I., Kearns, M. J., and Solla, S. A., editors, Advances in Neural Information Processing Systems, volume 10. The MIT Press.
Sniedovich, M. (2011). Dynamic Programming - Foundations and Principles (Second Edition).
Yang, R., Bhulai, S., van der Mei, R., and Seinstra, F. (2011). Optimal resource allocation for time-reservation systems. Performance Evaluation, In Press.
