The paper describes the construction of the motion and interaction model for agents with memory. Agents move on the landscape consisting of squares with different passability. We briefly characterize the cellular automata-based model with one common to all agents layer corresponding to the landscape and many agent-specific layers corresponding to an agent's memory. Also, we develop methods for the random landscape generation and the simulation of a communication system. Finally, we study a connection between the discrete agent motion model and the continuous concentration law for the system of agents.
1/2 and characterizes landscape heterogeneity in whole.
Definition 4. Total Edge Density (TED) of the landscape L is the ratio T E(L) to the total cell quantity N in the L
k [ S Worldag . ag=1
Let the objective reality layer OWorld consists of cells (i, j) ∈ Z2 with different impassability ui j. The value of ui j is the number of discrete time units which is required to pass the square ωi j with coordinates (i, j). If ωi j is completely impassable then put ui j = −1. Also cells can include the information about an agent in a cell, the agent’s destination square etc.
The subjective reality layer consists of cells (i, j) so that each its cell (i, j) corresponds the cell (i, j) of the objective reality layer. Cells of the subjective reality layer ag contain the information about the current position of the agent ag, about the history of the ag motion and about the impassability of known to the agent ag cells.
D = {(−1, −1), (−1, 0), (
M = {(i1, j1), (i2, j2), . . . , (is, js)|(ik, jk) ∈ Z2, k = 1, s, (ik+1 − ik, jk+1 − jk) ∈ D, k = 1, s − 1}, such as the agent in the square ωi1, j1 will be sequentially move into squares ωi2, j2 , . . . , ωis, js . Denote the set of all cellular routes starting in the cell with coordinates cA ∈ Z2 and ending in the cell with coordinates cB ∈ Z2 as M (cA; cB).
θ(x) = 0, x < 0, 1, x ≥ 0.
ψ3(u, Tmax) = u, u ≥ 0,
Tmax, u < 0.
T˜h(M) = X kdi jkψ3(ui j, Tmax). If cell impassability does not change over time, then it is not necessary to consider the routes containing impassable cells. However, if the impassable cell can become passable, these routes should be taken into account. To do this, define the functional We call weight of the route M for the agent ag the following: Λ(M; α, β, γ, Tmax) = αT˜h(M) + β X θ( fi j) + γ X visi j(ag),
The agent in the square ωi j each discrete time tick tries to find locally optimal (in a neighborhood Vo(i, j) with radius o) route Mo such that Λ(Mo; α, β, γ, Tmax) → min and go through this route. Therefore, the agent’s route at whole constructs from locally optimal subroutes.
Agent ag can apply previously described approach for route searching in undiscovered by this agent areas, i.e. in consisting of cells ωi j with visi j(ag) = 0. More standard approaches to optimum route search, for example, Dijkstra’s algorithm, can be used in areas composed of cells already visited. However, the use of standard methods of searching for an optimal route is limited to a rate of landscape change over time. It is possible that information about the visited cells become outdated (parameter timei j(ag) is used for determining the actuality of information), or even impassibility of the cells would change directly during the process of passing the route selected as the globally optimal.
Thus, depending on the speed of the landscape changes, it is necessary to find a compromise between the approach “Reacting”, which evaluates the current situation immediately near of the agent and the approach “Planning”, in which searched globally optimal trajectory. For example, it is pointless to set the radius o of the neighborhood Vo(i, j), in which agent searches locally optimal route more than the number of ticks during which the landscape has remained unchanged.
The example of the described cellular automaton is depicted on the fig. 1. Increasing of the impassability at the mentioned figure is indicated with a darker tone, crosses “×” in the layer S World mark already visited cells, marks “?” correspond to cells whose status is unknown.
Turn to the continuous formulation of obstacle avoidance problem to construct transfer function for our CA. The agent moves in the domain Ω with changing over time obstacles from the point A to the point B with route r(t), t ∈ [0, T ] in the shortest time T .
hold, define that square ωi j on the state in moment kτ ∈ [0, T ] is crossable in non-diagonal direction in ui j(k) ticks.
Moreover, it is possible to go to the integer values of the ui j(k) by discarding the fractional part and taking u˜i j(k) = [ui j(k)]. We associate with the agent in the square ωi, j value errci j of the cumulative discrete time error. Also we associate with the square ωi j error value erri j = {ui j(k)}. When an agent starts to cross the next square ωi′ j′ , the value errci′ j′ increments on the erri′ j′ , sets errci j = 0 and if errci′ j′ > 1 then agent passes one tick independently from the value of the function of obstacles in the square ωi′ j′ and sets errci′ j′ = errci′ j′ − 1.
Let
T : M (cA; cB) → R the functional of time which is required to going through cellular route.
If values of the ui j do not change in a time of the movement from the point A to the point B, then the problem (
kr˙(t)k = v(t, r(t)), r(0) = A, r(T ) = B,
T → min . th =
h max(i, j)∈Ih,k∈Tτ vikj(h, τ)
. ui j(k) =
h thvikj(h, τ) = max(i, j)∈Ih,k∈Tτ vikj(h, τ) vikj(h, τ) We will call further the function v : [0, T ] × Ω → R as “function of obstacles”. Divide the segment [0, T ] onto the k subsegments with length τ > 0, domain Ω onto squares ωi j with numbers (i, j) ∈ Z2 and the length of a side h. Approximate at each moment of time kτ ∈ [0, T ] on the square ωi j function v(kτ, ·) with the constant function vikj(h, τ).
T (M) = th X kdi jkui j → min .
Th(M) = X kdi jkui j → min
|r(l(t)) − rh(lh(t))| ≤ (h √2 + τ)(ek∇(t,x,y)vkC([0,T]×Ω)K − 1) + h √2,
(
Definition 7. Define the obstacle which is exists in the moment t ∈ [0, T ] as simply connected set Obst ⊂ Ω such that any robst ∈ Obst is the point of a local minimum of the function of obstacles v(t, ·) and exists r0 ∈ Ω such that v(t, r0) > v(t, robst).
Γ(t) = (Ag, Comm, ϕ(t), M(t)), where Comm is the set of channels, ϕ(t) : Ag × Comm → {0, 1} is the incidence function, M(t) : Comm → Rn is the markup function in the moment of time t ∈ [0, NT ]. The M gives the features vector of the channel comm ∈ Comm. This features can be channel bandwidth, radio frequency, etc.
Let’s introduce a communication graph connected with the motion model. This means that should be given the function pag : [0, NT ] × Ag → Z2 which maps agent’s coordinates to an agent in each moment t ∈ [0, T ]. Also, it means that M(t) and ϕ(t) depend on properties of cells in which incident agents are currently placed and on properties of cells between of them. Therefore, connections between agents in the Γ can break and establish depending on the agents’ speed and landscape type.
Suppose that each agent ag ∈ Ag has an own signal exchange timetable. It is possibly also to define specific signals like “enemy detecting”, “grouping”, etc. We can study various traffic models depending on the agents’ timetables, motion speed, and the landscape type.
Finally, we can define “requirements graph” Π and state that communication graph Γ(t) should be similar with Π in some metric each moment of time. Such graph Π can be viewed as a fuzzy set of communication graphs, as an abstract container or as a generator of the stream of communication graphs.
Also, we developed the conflict model combined with the motion and communication model similar to described in the work [6] and its computer simulation “Bokohod.” Agents emerge different kinds of tactics and exchange signals without any external control.
Previously the author had developed the algorithm of the landscape generation with the given configuration entropy. This algorithm constructs the vector of numbers of cells in each class V = (N1, . . . , Nl) by the given entropy S as follows:
β(1 − βl) − (1 − β)lβl
S = − (1 − β)(1 − βl) S t e p 2. Use the found solution 0 ≤ β ≤ 1 and equation ln β + ln 1 − βl ,
1 − β N1 = N 1 − β 1 − βl to find N1,
S t e p 3. Compose the vector V0 = (N1, βN1, . . . , βl−1N1),
S t e p 4. Round the components of the V0 up to integers and obtain the vector V1 in this way. It is necessary to make rounding such that the sum of all components of V1 would be equal to N.
We generate landscape such as the discrete function of the obstacles u : Z2 → Z would have local maxima strictly in Nobst = Vl = βl−1N1 cells. The author thinks that this method gives more natural-like landscapes as it makes “generally passable” area with some hardly passable subareas. As it known from [5] we can make very different landscapes with the same configuration entropy. By this reason, we will use the special, CA-based way of the filling landscape with cells of different classes. This method guarantees slow, near linear increasing of the TED at the increasing of the entropy.
Examples of obtained landscapes are shown on the fig. 2, (a,b). Sample dependencies of the configuration entropy, TED, and
We set l = 9, n = m = 48, o = 6, choose Nobst ∈ {5} ∪ {10i|i = 1, 25} ∪ {255}. Generate landscape for the each Nobst value and perform the following experiment1. Let an agent moves from the cell ω11 to the cell ωnn 100 times according to the previously described algorithm. Next, we compute the time which is required for the experiment completion T biok and the time of the moving from the ω11 to the ωnn by linear straight route Ttiup. Then we calculate the mean value and standard deviation of the win of time for all of this series:
win = 510 Xi5=01 TTbtiiuopk .
1The raw data and the data processing program for all experiments are stored at https://www.researchgate.net/publication/316747096_The_ experimental_data_for_group_motion_of_agents_with_memory_with_the_program_in_Wolfram_Language. (a) S = 1.6, Nobst = 14 (b) S = 1.8, Nobst = 33 u(x, t) = u0 ( erf (ξ1(S ; x, t)) − erf (ξ2(S ; x, t))),
2 ξ1(S ; x, t) =
+ b1(S ; x), a(S ; x)
√t ξ2(S ; x, t) = a(S ; x) √t
+ sgn (48 − x)b2(S ; x),
It was found that the mean value of the win in transit time win and the configuration entropy of the landscape S are correlated with a correlation coefficient 0.959556 (see fig. 4). The win and the TED of the landscape are correlated with a correlation coefficient 0.964763. The orange line in the figure corresponds to the curve y = (S (Nobst) + 1) ln 9; the brown line corresponds to the curve
y = 0.922178 + 0.539383T ED(Nobst), where S (Nobst) and T ED(Nobst) are the entropy and the total edge density’s mean value of the landscape with Nobst obstacles.
Let’s study the dependence of the average number of agents on time moment and position on a landscape. We generate 150 random landscapes with the given entropy by the algorithm mentioned above. The group formed from u0 = 48 agents moves from the one side of the squared landscape to the opposite one. Compute dependence of the average (through all landscapes generated) number of agents u at the xth line of a landscape on the discrete time t, x = 1, xmax, xmax = 48. Thus, we find that this dependence is determined, mainly, not by the particular kind of landscape, but by the landscape configuration entropy S . We found the dependence in the form where sgn (x) = 1, x > 0,
−1, x ≤ 0. u(x, t) = u20 erf 2xa−√l1t − erf 2xa−√l2t .
a(S ; x) = a1(S )x + a2(S ), b1(S ; x) = b11(S ) √x + b12(S ) + b13(S )
x3/2 , b2(S ; x) = b11(S ) √x + b22(S ).
This form of ξ1 and ξ2 parameters was assumed by the analogy with the problem of heat propagation along a rod with a thermal diffusivity a heated on its segment [l1, l2] to the temperature u0. This problem has (see, for example, [7]) solution
These functions allow to approximate u = u(x, t) with the coefficient of determination r2 > 0.97, the mean absolute error MAE < 0.1251, and the median absolute error MedAE < 0.04366 with every value of the entropy S . Experimental and approximated values of u are shown on the fig. 5. For example, when Nobst = 20 (S = 1.67909) u(x, t) = 24 erf −2.04693x√−t 1.03949 + 4.6x63/4238
− erf −2.04693x√−t 1.03949 + 1.08597 √x + sgn (48 − x)0.845118 .
Next, we try to find a problem for a partial differential equation which can have a solution in the form (
Let us denote ∂u ∂2u ∂u ∂t = C1 ∂x2 + C2 ∂x , u(x, 0) = u0δ(x − 1), δ(x) = 1, x = 0, 0, x , 0, lim(x, t) = u0θ(x − xmax), t→∞ θ(x) = 1, x ≥ 0.
0, x < 0,
U1(x, t) = e U2(x, t) = e
− a(S√;tx) +b22(S )+b11(S ) √x − a(S√;tx) +b11(S ) √x+b12(S )+ bx133/(2S) 2
MathematicalModeling/A.V.Kuznetsov
Compute from the (
2 √πt3
∂∂ux(x, t) = −
u0 x2(U1(x, t) − U2(x, t)) 2a1(S) √x + b11(S) √t + 3b13(S) √tU2(x, t)
2 √πtx5
,
(
C1(x, t) = QP11((√√xx,, √√tt)), C2(x, t) = QP22((√√xx,, √√tt)), where
Q1( √x, √t) = −3b11(S)tx2 4a1(S)2x13/2(b12(S)−b22(S))−2b13(S)x3 2a1(S)x(a1(S)x+a2(S))−2a1(S) √tx(b22(S)−2b12(S))+t + + b13(S)2 a1(S) √tx5 + 3a2(S) √tx3 + 3b12(S)tx3/2 + 3b13(S)3t + a1(S) 8a1(S)2 √tx9(b22(S) − b12(S))+ + b13(S) 4a1(S) a1(S) √tx15 + 3a2(S) √tx13 − 12a1(S)tx13/2(b22(S) − 2b12(S)) + 15t3/2x11/2 − − 6b13(S)2tx4 −a1(S)x + 3a2(S) + 3b12(S) √t − 18b13(S)3t3/2x5/2 + 3b11(S)2t3/2x4 b13(S) 3a1(S)x5/2 + a2(S)x3/2− − (b22(S) − 2b12(S)) √tx3 + 2a1(S)x4(b22(S) − b12(S)) − b13(S)2 √t + b11(S)3t2x6 x3/2(b22(S) − b12(S)) + 2b13(S) , + 2a2(S)b11(S)2tx11/2 + 2b11(S)3t3/2x6 + b11(S)t3/2x5 . (8) 3rdInternationalconference“InformationTechnologyandNanotechnology2017” Q2( √x, √t) = 2 t −3b11(S )tx2 4a1(S )2 x13/2(b12(S ) − b22(S )) − 2b13(S )x3 2a1(S )x(a1(S )x + a2(S ))− √
√ √ − 2a1(S ) √tx(b22(S ) − 2b12(S )) + t + b13(S )2 a1(S ) tx5 + 3a2(S ) tx3 + 3b12(S )tx3/2 + 3b13(S )3t + √ √ + a1(S ) 8a1(S )2 √tx9(b22(S ) − b12(S )) + b13(S ) 4a1(S ) a1(S ) tx15 + 3a2(S ) tx13 − − 12a1(S )tx13/2(b22(S ) − 2b12(S )) + 15t3/2 x11/2 − 6b13(S )2tx4 −a1(S )x + 3a2(S ) + 3b12(S ) √t − 18b13(S )3t3/2 x5/2 + + 3b11(S )2t3/2 x4 b13(S ) 3a1(S )x5/2 + a2(S )x3/2 − (b22(S ) − 2b12(S )) √tx3 + 2a1(S )x4(b22(S ) − b12(S )) − b13(S )2 √t + + b11(S )3t2 x6 x3/2(b22(S ) − b12(S )) + 2b13(S ) , √ P1( √x, √t) = −3b13(S ) tx13(a1(S )x + a2(S )), √ √ P2( √x, √t) = x5/2(a1(S )x + a2(S )) −b13(S ) 4 4a1(S )2 x5 + 6a1(S )a2(S )x4 + 7a1(S )b11(S ) tx9 + 3a2(S )b11(S ) tx7 + √ √ +24a1(S )b12(S ) √tx4+tx3 10b11(S )2 x+12b11(S )b12(S ) √x+15 +6b13(S )2 −a1(S ) tx5+3a2(S ) tx3+b11(S )tx2+3b12(S )tx3/2 − √ 2 − 2x11/2(b22(S ) − b12(S )) 2a1(S ) √x + b11(S ) t + 18b13(S )3t .
The form of coefficients a1(S ), a2(S ), b11(S ), b12(S ), b13(S ), b22(S ) depends on the landscape generation way. If we generate landscape as described before then we can approximate these parameters as follows where Results of such approximation are shown into the fig. 6, x = xmax = 48.
a(S ) = α(S )a(20), b1(S ; x) = β1(S )b1(20; x), b2(S ; x) = β2(S )b2(20; x),
10 α(S ) = 0.000344002 + 1.00018,
MAE < 0.001,
Note that we obtain different results by different landscape generation procedures. The general form of the function u will be
still described by the (
We obtained dependence of the win of movement by the proposed algorithm on the landscape’s configuration entropy for some types of landscapes. The immediately following result may be a comparison of a model of the conflict based on the proposed cellular automaton with the result of solution of the corresponding Osipov-Lanchester equations. Also, we compare models of the “diffusion” of agents into a given sub-area based on the cellular automaton with the solution of the corresponding reaction-diffusion type equation. Finally, we can simulate the sharing of the subjective reality layers between agents. In this case, one agent will use the information about the area, received from other agents and will transmit such information to other agents itself. The algorithm described in the article can be applied to the mobile robot equipped with a transport base, navigation equipment (compass, GPS receiver, etc.), a sensor allowing to determine the impassibility of the terrain and the deciding unit, including memory.