An analysis of reward shaping for reinforcement learning in a multi-agent framework for combinatorial optimization

• Jardell Fillipe da Silva CEFET-MG / UFV
• Maria Amélia Lopes Silva CEFET-MG / UFV
• Sérgio Ricardo de Souza CEFET-MG

DOI: https://doi.org/10.5753/eniac.2022.227627

Resumo

Este trabalho avalia modelagens de recompensas para o algoritmo de aprendizado usado por um framework multiagente para otimização combinatória. Esta avaliação consiste em seis cenários diferentes de modelagem de recompensas, aplicados a um conjunto de agentes idênticos construídos no framework, que implementam a metaheurística Iterated Local Search (ILS) para a solução do Problema de Roteamento de Veículos com Janelas de Tempo. Testes computacionais, aplicados a instâncias da literatura, mostram que os resultados obtidos para as diversas formas de recompensa são comparáveis quanto a qualidade dos valores de função objetivo alcançados, ao tempo de execução, e à velocidade de aprendizado frente a resultados já existentes na literatura. As conclusões mostram que é possível definir uma forma de aprendizado que seja autônoma quanto ao conhecimento do problema objeto de interesse e eficiente no que diz respeito a tempo computacional e velocidade de aprendizado.

Referências

Agogino, A. K. and Tumer, K. (2008). Analyzing and visualizing multiagent rewards in dynamic and stochastic domains. Autonomous Agents and Multi-Agent Systems, 17(2):320-338.

Devlin, S., Yliniemi, L., Kudenko, D., and Tumer, K. (2014). Potential-based difference rewards for multiagent reinforcement learning. In Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems, pages 165-172.

Feo, T. A. and Resende, M. G. C. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 6:109-133.

Grzes, M. (2017). Reward shaping in episodic reinforcement learning. Autonomous Agents and Multi-Agent Systems.

Lourenço, H. R., Martin, O. C., and Stützle, T. (2003). Iterated local search. In Glover, F. and Kochenberger, G. A., editors, Handbook of Metaheuristics, volume 57 of International Series in Operations Research & Management Science, chapter 11, pages 321-353. Kluwer Academic Publishers.

Mladenović, N. and Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11):1097-1100.

Silva, M. A. L., de Souza, S. R., Souza, M. J. F., and Bazzan, A. L. C. (2019). A reinforcement learning-based multi-agent framework applied for solving routing and scheduling problems. Expert Systems with Applications, 131:148 - 171.

Silver, D., Singh, S., Precup, D., and Sutton, R. S. (2021). Reward is enough. Artificial Intelligence, 299:103535.

Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 2(35):254-264.

Sutton, R. S. and Barto, A. G. (2018). Reinforcement learning: An introduction. MIT press.

Toth, P. and Vigo, D. (2014). Vehicle routing: problems, methods, and applications. SIAM.

Watkins, C. J. C. H. and Dayan, P. (1992). Q-learning. Machine Learning, 8(3):279-292.