1. Introduction
The search can be either complex or simple. When not known (or only partially known) both the goal itself and the way to achieve it, chance is important
The aim of the research article is to compare the methods of finding the target as moving (yellow object), and motionless.
These methods:
- Random search (red object)
- Random search with memory (blue object)
- Random search with memory and hierarchy (green object)
- Search for the first route (purple object)
- Search for a short route (brown object)
In Fig. 1, these objects are shown. Fully program code posted on
github
2. The main part
2.1. Class P - Random Search
The constructor initializes class attributes and variables: main window, color, y and x coordinate, counter, visited dictionary, target, hierarchy dictionary, neighbors dictionary. The init_3_dict method populates three dictionaries. The show method paints the cell in the desired color. The update method updates the object. The top_show method creates a top-level window and shows how many steps are taken to the target.
class P(): def __init__(self, root, color, node, target, maps, ban): self.root = root self.color = color self.y = node[0] self.x = node[1] P.target = target self.count = 0 self.visit = {} P.hierarchy = {} P.neighbor = {} self.init_3_dict(maps, ban)
The is_en function is declared in the init_3_dict method, which checks that the coordinate is not banned and does not go beyond the map.
def init_3_dict(self, maps, ban): def is_en(yx): if yx[0] < 0 or yx[0] > len(maps)-1: return if yx[1] < 0 or yx[1] > len(maps[0])-1: return if yx in ban: return return True
In a cycle, in the dictionary visited with the coordinate key, write the initial value zero. In the hierarchy dictionary with the same key, write the hierarchical name of this coordinate. Then we fill in the dictionary of neighbors by calling the is_en function.
for y in range(len(maps)): for x in range(len(maps[0])): self.visit[(y,x)] = 0 P.hierarchy[(y,x)] = maps[y][x] n = [] if is_en((y-1,x)): n.append((y-1,x)) if is_en((y+1,x)): n.append((y+1,x)) if is_en((y,x-1)): n.append((y,x-1)) if is_en((y,x+1)): n.append((y,x+1)) P.neighbor[(y,x)] = n
The show method paints a cell with y, x coordinates in the desired color.
def show(self, y, x, color): lb = Label(text=" ", background = color) lb.configure(text=P.hierarchy[(y,x)] ) lb.grid(row=self.y, column=self.x, ipadx=10, ipady=5, padx=1, pady=1)
The move method moves the object. In the variables y, x we write the coordinate of the neighbor, which is randomly selected from the list of neighbors. Then we redraw with the new coordinates.
We increase the counter. Check if the goal is achieved. If the goal is achieved, then in the variable of the class J.disable we write correctly. We call the top_show () method.
def move(self): v = [] for i in P.neighbor[(self.y, self.x)]: v.append(i) y,x = random.choice(v) self.show(self.y, self.x, 'white') self.y = y self.x = x self.show(y, x, self.color) self.count +=1 if P.target == P.hierarchy[(self.y, self.x)]: J.disable = True self.top_show()
The update method calls move and updates every half second.
def update(self): self.move() self.root.after(500, self.update)
The top_show method displays the results.
def top_show(self): top = Toplevel() lbt = Label(top, text=self.color + " = " + str(self.count)) lbt.pack() top.mainloop()
2.2. Class M - Random Memory Search
The constructor calls the constructor of the parent class and increases the value of the cell of the field where we are going. The move method moves the object. The choice method returns the coordinate that the random search algorithm with memory has selected.
In the move method, call the choice method. Otherwise, his work is similar to the parent's method.
def move(self): yx = self.choice((self.y, self.x))
The choice method iterates over the coordinates of neighbors and adds tuples to the list v. The first element of the tuple will be the coordinate of the neighbor, the second - how many times it has been visited. Then we sort from small to large. We sort through all the tuples and in the list v we leave only those that occurred as many times as recorded in the first tuple. Randomly select any of them.
def choice(self, yx): v = [] for i in P.neighbor[yx]: v.append((i, self.visit[i])) v.sort(key = lambda x: x[1], reverse = False) v = [i for i in v if v[0][1] == i[1]] v = random.choice(v) self.visit[v[0]] += 1 return v[0]
2.3. Class N - random search with memory and hierarchy.
The choice method selects those tuples that most closely match the hierarchical name of the target. If this match is the same, then the coordinates that were least visited are selected.
The constructor calls the constructor of the parent and initializes the coincidence attribute the number of character matches of the hierarchical name with the target.
def __init__(self, root, color, node, target, maps, ban): super().__init__(root, color, node, target, maps, ban) self.coincidence = 0
The choice method in the loop writes the hierarchical name of the current coordinate of the neighbor. The variable r stores the number of matches of this variable with the target. If the number of matches r is greater, then coincidence is overwritten. In this case, the tuple (coordinates, number of visits) from the list v is written to the list d. If r is equal to coincidence, then in d we add a tuple from v.
def choice(self, yx): v = [] for i in P.neighbor[yx]: v.append((i, self.visit[i])) d = [] for l in v: c = P.hierarchy[l[0]] r = 0 for i in range(len(P.target)): if c[i] == P.target[i]: r +=1 else: break if r > self.coincidence: self.coincidence = r d = [l] if r == self.coincidence: d.append(l) if d: v = d v.sort(key = lambda x: x[1], reverse = False) v = [i for i in v if v[0][1] == i[1]] v = random.choice(v) self.visit[v[0]] += 1 return v[0]
2.4. Class K - search for a route and search for the shortest route.
The constructor writes end coordinates to the end variable. If the short parameter is False, then we call the route search. Otherwise, we find the shortest route.
The find_path method adds the current coordinate to the route. If the goal is reached, then returns the route. We sort through all the neighbors. If there is no neighbor in path, then call ourselves recursively. And the fact that the method returns is written to newpath. The first route found will be newpath. The difference between the find_short_path method is that if the length of newpath is greater than or equal to the length of shortest, then shortest is overwritten.
def find_path(self, node, end, path=[]): path = path + [node] if node == end: return path for v in P.neighbor[node]: if v not in path: newpath = self.find_path(v, end, path) if newpath: return newpath
2.5. Class J is a moving target.
An object of class J moves like class P. If the variable of class J.disable is true, then the object stops.
2.6. Function main.
Create the main window. In the target variable, write the hierarchical name of the target. The ban list contains the coordinates of the forbidden cells. In the list of maps, the map itself. In the loop we draw a map. Create class objects. Then we call the update function, which updates the objects.
3. Conclusions
Five experiments were carried out both for a moving target and for a motionless one.
Table 1 shows that the best algorithm is the shortest route. The second most effective is a random search with memory and hierarchy. The worst is random search.
Table 1. Fixed target
In the case of a moving target, the results are different. The worst algorithms were those that initially calculated the route to the goal. In table 2, a dash indicates that the goal has not been achieved. Brown turned out to be worse than Violet. Worse, because Violet has a longer trajectory (the chance to meet a moving target is greater). The best algorithm when searching for a moving target is a random search with memory and hierarchy. In second place is a random search with memory.
Table 2. Moving Target
If it is not known whether the target is moving or not, then it is better to use the random search algorithm with memory and hierarchy or just random search with memory.
4. Conclusion
Randomness is important if the search for a target occurs in the face of uncertainty. Search is reduced if data is presented hierarchically. Memory, of course, is also valuable.