ISSN 2071-8594

Russian academy of sciences

Editor-in-Chief

Gennady Osipov

M. A. Rovbo, E. E. Ovsyannikova Methods of local behavior planning for agents with BDI architecture

Abstract.

The paper deals with the possibility of solving a collective task by a group of intelligent agents with the BDI architecture using three different methods: planning using a global announcement board, coordination through local boards and the exchange method. The new method proposed in the article is the local boards method based on the modification of the global board method. Also the analysis of the exchange method with the proposed formalization and application of the polynomial reduction method was conducted. All three methods were implemented on a simple simulation of the task of assisted movement on a grid, which explored the applicability of the architecture and methods for a real mobile multi-agent system. The special features of the task are the difficulty of maintaining a common communication channel and the limited computational resources. It was shown that this problem can be solved by introducing local announcement boards, when each agent makes a decision based on access to the advertisements of its neighbors. An analysis of the method based on exchanges has shown that it can be reduced to the formulation of the STRIPS problem. The exchange method allows to make a search on a smaller graph in comparison to the STRIPS method.

Keywords:

BDI architecture, multi-agent system, behavior planning, agent cooperation.

PP. 74-86.

DOI 10.14357/20718594190107

References

1. Cohen, P. R., & Levesque, H. J. 1991. Teamwork. Noûs 25(4):487–512. doi:10.2307/2216075.
2. Kalyaev, I. A., Gaiduk, A. R., & Kapustyan, S. G. 2009. Modeli i algoritmy kollektivnogo upravleniya v gruppakh robotov [Collective control models and algorithms for groups of robots]. Moscow: Fizmatlit. 280 p.
3. Grosz, B. J., & Kraus, S. 1996. Collaborative Plans for Complex Group Actions. Artificial Intelligence 86(2): 269–358.
4. Kulinich, A. A. 2017. Model' komandnogo povedeniya agentov v kachestvennoi semioticheskoi srede. Chast' 1. Kachestvennaya sreda funktsionirovaniya. Osnovnye opredeleniya i postanovka zadachi [Model of team behavior of agents in a qualitative semiotic environment. Part 1. Qualitative operating environment. Basic definitions and problem statement]. Iskusstvennyi intellekt i prinyatie reshenii [Artificial intelligence and decisionmaking] (3):38–48.
5. Kulinich, A. A. 2016. Stainye algoritmy formirovaniya i funktsionirovaniya komand agentov [Pack algorithms of formation and functioning of teams of agents]. In Trudy kongressa po intellektual'nym sistemam i informatsionnym tekhnologiyam «AIS-IT’ 16» [AIS-IT’ 16]. pp. 301–310. Taganrog: Izd-vo “YuFU.”
6. Rao, A. S., & Georgeff, M. P. 1995. BDI Agents: From Theory to Practice. Proceedings of the First International Conference on Multiagent Systems. 95: 312–319.
7. Kulinich, A. A. 2018. Model' komandnogo povedeniya agentov v kachestvennoi semioticheskoi srede. Chast' 2. Modeli i algoritmy formirovaniya i funktsionirovaniya komand agentov. [Model of team behavior of agents in a qualitative semiotic environment. Part 2. Models and algorithms for the formation and functioning of teams of agents] Iskusstvennyi intellekt i prinyatie reshenii [Artificial intelligence and decision-making]. (1): 29–40.
8. Karpov, V. E., Karpova, I. P., & Kulinich, A. A. 2019. Sotsial'nye soobshchestva robotov [Social communities of robots]. Moscow: URSS. 352 p.
9. Karpov, V. E., & Meshcheryakova, T. V. 2004. Ob avtomatizatsii netvorcheskikh literaturnykh protsessov [Automating noncreative literary processes]. Informatsionnye tekhnologii [Information technologies]. (8): 56–63.
10. Vittikh, V. A., & Skobelev, P. O. 2003. Multiagent Interaction Models for Constructing the Needs-and-Means Networks in Open Systems. Automation and Remote Control. 64(1): 162–169. doi:10.1023/A:1021836811441.
11. Conte, R., & Castelfranchi, C. 1996. Simulating Multi- Agent Interdependencies. A Two-Way Approach to the Micro-Macro Link. In Social Science Microsimulation. pp. 394–416.
12. Osipov, G. S. 2011. Metody iskusstvennogo intellekta [Artificial intelligence methods]. Moscow: Fizmatlit. 296 p.
13. Fikes, R. E., & Nilsson, N. J. 1971. Strips: A new approach to the application of theorem proving to problem solving. Artificial Intelligence 2(3–4): 189–208. doi:10.1016/0004-3702(71)90010-5.
14. Bäckström, C. 1995. Expressive equivalence of planning formalisms. Artificial Intelligence 76(1–2): 17–34.
15. Bäckström, C. 1992. Computational Complexity of Reasoning about Plans. Doctoral dissertation. Linkoping University, Linköping, Sweden. 210 p.
16. Karpov, V. E. 2013. Upravlenie v staticheskikh royakh. Postanovka zadachi. [Control for static swarms. Problem statement] In Trudy VII-i mezhdunarodnoi nauchnoprakticheskoi konferentsii «Integrirovannye modeli i myagkie vychisleniya v iskusstvennom intellekte» [Proceedings of VII international scientific and applied conference "Integrated models and soft computation in artificial intelligence"]. pp. 730–739. Moscow: Fizmatlit.