Stochastic methods for modeling the topological operating environment of an autonomous mobile agent

Stochastic methods are used to model the topological operating environment of an autonomous mobile agent that performs goal-directed movement or navigation. For successful navigation, it is necessary to efficiently represent information about the environment, i.e. to create its map. The topological representation focuses on the structural characteristics of the environment and the connections between different areas of space. The model of this representation is a graph, where vertices represent important locations and edges represent possible paths between them. In this paper, the environment is modeled as a graph with labeled vertices, where agents can move autonomously by recognizing the labels on these vertices. This approach allows us to create an efficient navigation system without complex self-localization mechanisms. In this paper, we distinguish two types of labelling that uniquely define the paths of agents on the graph according to the corresponding sequences of vertex labels. These labellings are determined by constraints on the values of the labels in the neighborhood of each vertex of the graph and are called deterministic (D-) and strongly deterministic (SD-) labellings. Since the vertex labels can be interpreted as natural numbers, graph labelling can be considered as a special case of the vertex coloring. We consider the problem of constructing D- and SD-coloring on a graph. The power of the set of colors used should be as small as possible, ideally minimal. To solve this problem, we have studied the application of three most popular stochastic methods -- simulated annealing, ant colony optimization, and biological evolution - which have been shown to be effective for constructing proper coloring of large and complex graphs. We have developed the software prototypes of the algorithms for constructing D- and SD-coloring, based on these methods Also, the DSATUR algorithm, one of the most common greedy heuristics for constructing proper colorings, was modified to build D- and SD-coloring. We performed a series of computational experiments to build proper, D-, and SD-coloring using the developed algorithms and a wide range of control parameters. Experimentally, the advantage of the algorithm based on the simulated annealing method was revealed among other stochastic methods considered in the paper