key: cord-0047487-4o6o47ed
authors: Larkin, Eugene; Akimenko, Tatyana; Privalov, Aleksandr
title: Synchronized Swarm Operation
date: 2020-06-22
journal: Advances in Swarm Intelligence
DOI: 10.1007/978-3-030-53956-6_2
sha: 7a441429bdc30403d7e86907ef5a625fbefd5079
doc_id: 47487
cord_uid: 4o6o47ed

Physical swarm system, including number of units, operated in physical time according to corporative algorithm, is considered. It is shown, that for proper corporative algorithm interpretation it is necessary to synchronize computational processes in units. Structural-parametric model of synchronized swarm operation, based on Petri-Markov nets apparatus, is worked out. In the Petri-Markov net transitions are abstract analogues of synchronization procedure, while places simulate corporative algorithm parts interpretation by swarm units. Primary Petri-Markov model is transformed into complex semi-Markov process. Formulae for calculation of stochastic and time characteristics of the process are obtained. It is shown, that after transformation all methods of ordinary semi-Markov processes investigation may be used for synchronized systems. With use the concept of distributed forfeit effectiveness of synchronization is evaluated.

Physical swarms, which solve corporative task, are widely used in different branches of human activity, industrial and mobile robotics, concurrent computation, control systems, etc. [1] [2] [3] [4] [5] . Such systems include number of units, each of which operates accordingly to its own algorithm realized on Von Neumann type controllers. Due to consecutive interpretation of algorithm operators and accidental character of data processed, runtime of controller is a random value, and outcome of program operation is stochastic [6] . So for proper operation, when solving a corporative task, swarm should be tuned in such a way, that corporative algorithm should be divided on pieces, which are realized on swarm units, and interpretation of algorithm pieces should be carried out in the proper sequence [7] . Such alignment is called synchronization. For optimal synchronization adequate model of parallel process should be worked out. Below approach to simulation, based on Petri-Markov nets [8] , which from one side permits to evaluate random time intervals characteristics, and from other side take into account interaction of parallel processes, is used. Also for optimal synchronization it is necessary to have criterion, which permits to evaluate effectiveness of corporative algorithm division. Below universal criterion, called distributed forfeit, is proposed, and formulae for effectiveness estimation with use proposed criterion are obtained.

Approaches to simulation of synchronized operation of swarm are currently known insufficiently, that explains necessity and relevance of the investigations in this domain.

Operation of swarm, which includes M units and solves some corporative task, may be described with use Petri-Markov net (PMN) apparatus [8] . Swarm operation model is as follows (Fig. 1 

where A = A 1 , . . . , A j , . . . , A J is the set op places, which describes operation of M swarm units; Z = Z 1 , . . . , Z j , . . . , Z J is the set of transitions, which describes synchronization procedures; ι(Z) o(Z) are input and output functions of transitions, correspondingly; J number of operators in corporative algorithm of swarm behavior when solving corporative task;

PMN operation may be considered as sequence semi-steps, which may be done either from places to transitions, α j,0 , ζ j,0 , α j,m,j(e) , ζ j, 1 

For semi-step execution from places α j,0 , α j,1 , . . . , α j,m , . . . , α j,M into corresponding transitions random time interval t should be spent, which begins from the moment, when semi-step was done into this place. Time intervals are determined with an accuracy to time densities f j,

For semi-step execution from transition ζ j,0 simultaneously to all places α j,1 , . . . , α j,m , . . . , α j,M , constituting its output function o ζ j,0 only semi-step α j,0 , ζ j,0 should be done. For execution of one of semi-step from the transition ζ j,1 , the proper α j,m,j(e) , ζ j,1 semi-steps combination to named transition must be done, due to only one direction of the set {1(e), . . . , j(e), . . . , J (e)} may be choose for doing semi-step ( Fig. 1 ).

In such a way, transitions ζ j,0 , and ζ j,1 , are the synchronized one: transition ζ j,0 in the sense that all semi-steps, included into its output function o ζ j,0 , are executed simultaneously (synchronous start), but transition ζ j,1 in the sense, that semi-step from it would not be done until all semi-steps from places of ι ζ j,1 will be done.

PMN timing elements are places. Time of residence PMN at places α 1,0 , . . . , α j,0 , . . . , α J ,0 is as follows

where δ(t) is the Dirac δ-function.

is defined as the time of wandering through semi-Markov processes [9, 10] 

which are abstract analogues of swarm unit onboard computers operation, and are defined as follows (Fig. 2) :

where A j,m , A j,m = J (a) + 1, is the set of states, which are abstract analogues of swarm unit onboard computer algorithm operators; r j,m is the [J (a) 

The set A j,m is divided onto two disjoint subsets, subset of non-absorbing states

and subset of absorbing states E j,m . 

Wandering through states of semi-Markov process h j,m (t) start at the state a j,m,0(a) , which is the abstract analogue of "begin" operator. States a j,m,j(e) ∈Ē j,m are the abstract analogues of "end" operators for different outcomes of algorithm operation.

Element h j,m,j(a),n(a) (t) ∈ h j,m (t) performs weighted time density of m-th swarm unit residence in the state a j,m,j(a) when decision was made about next switch into the state a j,m,n(a) .

Weighted time density of the semi-Markov process μ j,m wandering from the state a j,m,0(a) till the state a j,m,J (a)−J (e)+j(e) ∈ E is as follows: 

Pure (non-weighted) time density, expectation and dispersion are equal, correspondingly [13] 

With use formulae (13), (14) , (15) obtained, Petri-Markov sublet, circled on the Fig. 2 with dashed line, may be replaced with the single state, and so the PMN may be replaced with complex semi-Markov process, which describes behavior of the swarm as a whole. Circled with dashed line subset is as follows 

Semi-Markov process is as follows

where B = b 1 , . . . , b j , . . . , b J is the set of states, which are abstract analogues of execution by swarm the complex operation due to algorithm of swarm behavior; r = r j,n is the J ×J adjacency matrix; h j,m (t) = h j,n (t) is the J ×J semi-Markov matrix.

Let us define probabilities and time densities of switch from the complex state b j ∈ B to the complex state b n ∈ B. Semi-steps α j,0 , ζ j,0 and ζ j,0 , α j, 

From (25) may be selected those vectors, combination of trios of which permit to do emi-step ζ j,1 , α n,0 : 1, i(e, n) , . . . , j, m, j(e, n) , . . . , j, M , k(e, n) , j, 1, l(e, n) , . . . , j, m, q(e, n) , . . . , j, M , s(e, n) ;

Probability of κ(n)-th combination emergence is as follows:

So, probability p j,n of switch the complex semi-Markov process μ from b j to b n is equal to the sum

For calculation of time density f j,n (t) one should consider the competition [9, 14] on the transition ζ j,1 between ordinary semi-Markov processes μ j,m . Residence at the state b j is considered as completed, when last ordinary semi-Markov process reaches its E j,m state according the combination (25). This is why semi-Markov processes compete for not being the last in the competition. Time of reaching subset E j,m by all M may be described with the following formula: (31)

After transformation for investigation of swarm behavior investigation and calculation of wandering time intervals all possible methods of semi-Markov process analysis may be used [9] [10] [11] [12] .

One of the important aspects of swarm operation organization is elimination of unproductive units downtime when corporative task is solved. Parameter, which defines effectiveness, may be any, but when investigation of relay-races, distributed forfeit is of widely used. Let us considered competition of m-th i l-th swarm units, first of which gets the transition ζ j,1 during time f j,m,j[e,κ(n)] (t), but second -during the time f j,l,j[e,κ(n)] (t). In the case of winning in competition the first swarm unit he waits until l-th swarm unit gets ζ j,1 . Waiting time is calculated as follows [15] :

where τ is an auxiliary argument; η(t) is the Heaviside function. Probability of such event, expectation and dispersion of waiting time are as follows 

Every of value (34), (35), (36) may characterized those or that effectiveness aspect, but more universal is the criterion, which is defined as distributed forfeit [15] 

Sum C j(b),m depends on parameters of ordinary semi-Markov processes (7), and forfeit discipline. Such sum may be used as optimization criterion in the task of producing optimal swarm behavior.

Working out the model of swarm synchronized operation opens new page in parallel systems theory because it permits to link real physical parameters of hardware with structure and logics of operation oh corporative algorithm, distributed among swarm units. Algorithm splitting may be done with those or that way, but with use approach proposed, swarm program designer for every mode of splitting may evaluate main characteristics both corporative algorithm as a whole, and parts of it, realized on swarm units.

Further investigation in this area should be directed to working out an algorithm splitting optimization method, based on proposed approach to parallelization modeling and evaluation of effectiveness.

The research was supported by the Foundation for Basic Research under the project 19-47-710004 r_a.

Introduction to Mobile Robot Control

Stochastic analysis and optimization of multiserver systems

Digital Control Systems, Design, Identification and Implementation

Computer Controlled Systems: Theory and Design

Estimation of latency in embedded real-time systems

An Introduction to Parallel Programming

Petri-Markov model of fault-tolerant computer systems

Competition and cooperation between brands in a segment: an analysis based on a semi-Markov model

Applied Semi-Markov Processes

Event-driven semi-Markov switching state-space control processes

Semi-Markov modelling of commands execution by mobile robot

Probability, Random Processes and Statistical Analysis

Concurrency and composition in a stochastic world

Simulation of Relay-races