Tkachev K.  

Use of multi-agent in simulation and optimization

Use of multi-agent in simulation and optimization*

 


Author Tkachev K.V.

ICM&MG SB RAS, Prospekt Lavrentieva, 6

Novosibirsk, Russia, 630090

Novosibirsk State University,

Str. Pirogova 1, Novosibirsk, Russia, 630090

Tkachyovkv@yandex.ru

 


AbstractUsage of agent-observer in simulation optimization, especially in optimizing system behavior is discussed in the paper. The agent allows you to observe, for the dynamics of changes in the parameters and behavior of the model. Changing some parameters leads to a significant reduction in simulation time.

Keywords—agent; behavior and strategy optimization

The research was under the partial financial support of the Russian Foundation for Basic Research (project No. 17-07-00775).

                                                                                                                                                      I.      Introduction

The development of simulation methods and tools began in the middle of the last century. Modern information technologies made it possible to model huge systems. In these systems, a huge number of different components are used that respond to many different events [1]. When using simulation, you often have to deal with systems designed for reusing when solving similar problems. Good example of such systems is queuing networks with large amount of servers belonging to small number of classes (telephone systems, computer complexes, ticket offices in large transport companies, etc).

To create simulation systems that support parallel discrete event simulation, developers use special processors for parallel modeling, low-level languages, special libraries and tools. Modern programming techniques and advantages of parallel and distributed computing environments give new possibilities for development of special simulation tools on the one hand, and bring new optimization tasks on the other hand. In the current paper, we consider tasks of finding optimal behavior of complex systems by using agent-oriented simulation [2].

                                                                                                                                              II.    agent-observer

Currently, there is a single concept of a software intelligent agent. There are general properties of the agent [2]. According to [3], the multi-agent system has some properties:

·         autonomy — agents operate without the direct intervention of humans or others;

·         social ability — agents interact with other agents via some kind of communication language;

·         reactivity — agents perceive their environment, and respond in a timely fashion to changes that occur in it;

·         pro-activeness — agents do not simply act in response to their environment, they are able to exhibit goal-directed behavior by taking the initiative.

Because of their properties, agents are ideally suited for modeling behavior of complex distributed systems. Agents are now very popular and widely used in various applications, including simulation [4]. In [5] the May simulation system is described that uses object-oriented presentation of a model and authors state that “distributed computer systems are most convenient for simulating distributed systems”. Now we can say that multi-agent systems are very suitable for parallel and distributed modeling of large distributed systems [3].

To implement the agent-based model, we propose create the agent-observer (AO), whose task is monitoring and modifying some parameters of the model due to a goal of simulation run. Let us divide the description of a model and an experiment. A separate software module describes simulation goals. Only this module requires recompilation for each experiment or series of experiments [4]. The main idea of this approach is the division of variables into observables and managed ones. The AO checks the achievement of the declared goals and conditions of the experiment and makes decisions about changes in the controlled variables and/or strategy of a model. Similar idea is implemented in the classic Simscript simulation language [6].

                                                                                                       III.   BEHAVIOR AND STRATEGY OPTIMIZATION

We use some concepts introduced in [1]:

·         the behavior of systems is a sequence of values of state variables that change as a result of processing certain events;

·         strategy is defined by choice of procedures for event handling;

·         meta strategy is defined by choice of strategy (strategy may change during simulation run depending on some events).

Behavior of a system is composed from behaviors of its components that are realized by agents, so the task is finding such behaviors of agents that lead to a simulation goal.

To confirm the ideas, a model was created that allows testing various algorithms for managing a massive flow of events in a simulation model and analyzing the process of system control.

Let us consider the simulation model of repair works in electric networks. An event is the repair of a specific object in it. General characteristics of the model:

·         number of repair objects not less than 10000;

·         repair requires usage of contingent resources;

·         breakdown happens at random time;

·         there are 100 repair teams;

·         some failures are related;

·         there is a rating of importance of objects;

·         there is a coefficient responsible for duration of repair depending on a season of year, day of the month or week, etc.

Fig. 1 shows the interaction of the agent with the model. We denote certain parameters as observable, and some as controllable. In the model considered, the following parameters are assigned for each repair:

·         amount of resources and time the team needs for this repair;

·         how many objects are not workable at the moment;

·         is this repair related to another?

·         Time of year and day of the month;

·         how many important facilities fail?

Control variable:

·         the boundary of importance of an objects;

·         the total cost of repairs for a certain period;

·         the admissible number of disabled objects;

·         restrictions on time of repair.

Fig. 1.    Scheme of controllable experiment

                                                                                                                                                        IV.   Experiment

In this model, the following strategies for choosing the order of repairs are considered (processing events in a certain sequence):

·         random selection;

·         selection according to the importance of the object;

·         minimizing the cost of work;

·         minimizing damage.

Restrictions, violations of which lead to non-fulfillment of the purpose of modeling:

·         limit waiting time for repair;

·         resource limitations.

The tables show the results of the simulation, provided that some parameters are changed at runtime.

TABLE I.             Time of simulation taking into account changing conditions

Change conditions

Without an agent

With an agent

Changing the time of year

3564.64

3258.15

Resource constraints

3489.87

3099.69

Minimization of damage

3698.15

2954.99

TABLE II.           Time of modeling in view of the choice of the repair procedure

Choice of repair procedure

Modeling time

Spent resources

Random selection

2689.95

100%

Selection according to the importance of the object

1649.12

112%

Minimizing the cost of work

2831.61

84%

Minimization of damage

1896.15

119%

TABLE III.         The simulation taking into account the time limits

Limit waiting time for repair

Modeling time

Spent resources

10000

2679.15

100%

1000000

1899.48

92%

100

3199.48

146%

TABLE IV.         The simulation taking into account the resource constraints

Resource limitations

Modeling time

Spent resources

100

2712.13

100%

1000

2196.82

98%

100000

1247.58

57%

 

Fig. 2.    An example of the work of a model and an agent-observer

                                                                                                                                                        V.    Conclusion

Experiments show that using an agent-observer during execution, allows controlling the dynamics of changes in parameters and behavior of the model. Changing some parameters leads not to a significant reduction in simulation time only, but to choosing best strategy of a system behavior.

References

[1]     A. Rodionov. Agent-oriented simulation: new advantages in simulation optimization. In Proceedings of the 11th International Conference on Ubiquitous Information Management and Communication (IMCOM '17). ACM, New York, NY, USA, Article 103, pp. 4-27, 2017.

[2]     M. Wooldridge, N. Jennings. Intelligent agents: theory and practice. Knowledge Eng. Review, pp. 152-189, 1995.

[3]     M. J. Wooldridge. An Introduction to MultiAgent Systems (2. ed.). Wiley,pp. 12-23, 2009.

[4]     A. Borshchev. XJ technologies: Anylogic 6. In Proceedings of the 37th Winter Simulation Conference, Orlando, FL, USA, December 4-7, 2005, pp. 82-101, 2005.

[5]     Bargodia R.L., Chandy K.M., Misra J. A Message-based approach to discrete-event simulation IEEE Trans. on Soft. Eng. Vol.  se-13, No 6, pp. 654-668, 1987.

[6]     R. M. Fujimoto. Distributed simulation systems. In Simulation Conference, 2003. Proceedings of the 2003 Winter, volume 1, pp. 124- 134, 2003.


 


To reports list