Navigation service robot on the golf course. Construction and obstacle avoidance

What method of navigation and obstacle avoidance is optimal for a service robot?

Robots are software-mechanical complexes interacting with the real world. For a service robot, it is extremely important to understand your current position in space, the position of the target, and the ability to build a route to the target, bypassing possible obstacles. We develop a robot for collecting golf balls in the driving range . We considered various options for constructing a route in order to find the best one for ourselves, perhaps this information will be interesting to someone.

The easiest way is to route the robot to its ultimate goal in two-dimensional space. The rover itself here is a small point, in front of which there are no obstacles. Therefore, in such a situation, the robot moves in a straight line, and when it reaches the goal, it stops.

This method is suitable if the world is exclusively a robot and a goal that it must achieve. Direct will allow you to reach the final configuration as quickly as possible.

')

But this algorithm cannot be applied if an obstacle suddenly appeared in front of the robot. Moving in a straight line, the rover will not be able to go around it or go through. In this connection, he simply stops in front of an obstacle and does not move on.

How to get around an obstacle? The easiest way to solve the problem will help the option of behavior, called "avoiding obstacles." In practice, it is represented by various algorithms.

Algorithm Walk To

If the goal is not achieved:

Move to the goal.
Otherwise: stop.

This method is suitable if the world is exclusively a robot and a goal that it must achieve. Direct will allow you to reach the final configuration as quickly as possible. But what algorithm to apply, if an obstacle appeared on the way to the target in front of the robot?

The obstacle prevents the robot from reaching its destination in a straight line, in this situation the rover simply stops in front of it. In this case, you can also use the "Walk To" algorithm, but it needs to be supplemented.

Bug Algorithm

In ordinary life, a person, when he goes from one point to another to the goal and stumbles upon an obstacle, simply bypasses it. This behavior is called "avoiding obstacles." It can be applied to achieve the goal of the robot. The easiest way is to use the beetle algorithm.

The Bug algorithm is named by experts precisely this way because the beetle's behavior is taken as the basis here - if it sees an obstacle, it bypasses it.

The steps that a robot goes through while moving to a target (including when avoiding an obstacle) are called a trajectory.

The beetle algorithm served as the basis for the concepts that are used in constructing routes of a more complex type. These include:

Trajectory concept. This is a simple sequence of movements of the robot, which he performs to achieve the ultimate goal. The beetle algorithm is also the “Path Planner”. Having obtained the coordinates of the points where the robot and its target are located, the algorithm develops an appropriate trajectory of movement.

The concept of politics . If using the beetle algorithm, the robot transmits certain instructions for moving, then this method of constructing a route is referred to as the “Management Policy”.

The concept of heuristics. This is the name of the rule used to inform the robot about the further stage of the algorithm. In this situation, the heuristic is the line along which the object moves. When creating a path, it is necessary to correctly determine heuristics. If you do this incorrectly, then the constructed route will not work.

However, such an algorithm limits the developer, because with his help it will be possible to build a route that is limited in size. When using such an algorithm for constructing a path, it is necessary that all obstacles take the form of a convex polygon.

Also, the Bug algorithm has limitations:

obstacles must be at a certain distance from each other, it is impossible that they have points of contact;
the boundaries of the obstacles are closed curves, while they must be such that the straight line along which the robot moves intersects each of them a limited number of times;
the robot is a disproportionately small point, so it can move between obstacles regardless of the passage between them.

Some of these limitations will be overcome if we use the improved DH-Bug algorithm. Its feature is that with its help the robot will be able to cope with moving obstacles. Moreover, such an algorithm consists of two layers. The first is an advisory one. It allows you to pre-evaluate the route without using additional information. The second layer is adaptive. Thanks to him, the robot promptly responds to the obstacles that have arisen, which were not originally laid in the program.

CBUG algorithm

The CBUG algorithm is a version of constructing a route in such a way that all the details are taken into account. During its development, specialists took into account the size of the robot, and also resolved issues related to the optimization of the path being created. A distinctive feature of such an improved algorithm is that to generate a route, it is necessary that the starting point always remain in the memory of the object. Unchanged for the CBUG algorithm, only that in order to use it, it is necessary to have a fixed amount of memory.

Dijkstra's Algorithm

The algorithm, which is used on graphs, was created by E. Deikstroy in the second half of the last century. With it, you can determine the shortest path from one of the vertices of the graph to the others. Such an algorithm is completed at the moment when the robot visited all the vertices. If you skated those that he has not yet visited, then select a vertex with a minimum mark.

The advantages of Deuster’s algorithm include:

paying attention to the length of the path and its cost;
nodes are updated in case more optimal was found.

The disadvantage of this method of constructing a route is that it is suitable only for graphs where there are no negative weight edges. It is also inconvenient that it is poorly oriented when searching in width.

Bellman-Ford Algorithm

But often there are situations in which you need to build a route, where there are edges with a negative weight. The Bellman-Ford algorithm will help solve this problem. If, as a result, the sum of the weights of the edges takes a negative value for the final path, then it is called a negative cycle.

Johnson's algorithm

This algorithm was introduced by D. B. Johnson in order to determine all the shortest routes from one vertex to another. In this case, the method can be used for edges with both positive and negative weight. The only drawback of the algorithm is that there are no negative cycles.

Algorithm A *

To find the most optimal way using graphs, you need to apply the algorithm A *. It allows you to determine the best route from the robot to the target by the first match on the graph. This algorithm is based on a heuristic formula that looks like this:

f(n)=g(n)+h(n).
    

      
      
      
    

  f(n) - , n.
    

      
      
      
    

  g(n) - n .
    

      
      
      
    

  h(n) - .

This algorithm allows you to find the shortest path to the target until h (n) accepts the maximum allowed value. A feature of the algorithm A * in its flexibility. Most often, the state is the cell or location of the robot. But it can also be speed or orientation.

At the same time, nearby states vary depending on the specific case.

The flexibility of the algorithm is manifested in the fact that the goal to be achieved by the robot can consist of several positions at once. In such a situation, the heuristic approximation h (n) should be valid for all available targets at once.

How well the algorithm A * will work depends on the indicator h (n). The better the quality of heuristic approximations, the higher the efficiency. Also, the work of the algorithm is affected by the amount of free memory and processor time.

Wave trace algorithm

Also, a wave algorithm is often used to compile a route on a graph. When constructing a path in this way, the search method is used in width.

The algorithm itself includes the following steps:

initialization;
wave construction;
route recovery.

At the initial stage, an image of a plurality of cells is created, each of which becomes either passable or impassable for the robot.

The robot, moving from one cell to another, sequentially determines whether it is possible to go through it and did not mark it earlier.

After this, the search method creates the shortest path from the starting cell to the final one, the achievement of which is the goal of the rover.

Discretize Space Algorithm

The configuration space has the same size in all dimensions.
Discrete all measurements so that they contain a constant number of cells.
All cells located in the configuration space inside the obstacle should be marked as impassable.
As a result, all passable cells turned into nodes.
Each node connects with all neighbors in the graph.

Randomized search path

The most difficult aspects when planning a route are the calculation of the configuration space and the determination of the most convenient path when passing through this space. Thanks to the roadmaps it will be possible to solve these problems. The essence of the method is to divide the space into identical squares, the connection of all the nearest vertices. Enumerate all paths. Sort all the paths to find the path with the lowest value.

Algorithm Probabilistic Road Maps

1. Create an empty graph G.
2. Add to the graph G nodes of the robot and its ultimate goal.
3. For the N-th number of integrations:
1. Find a homogeneous random sample of the configuration space and give it the name R.
2. If the robot is in collision with configuration R, then you can continue.
3. Otherwise: add R to column G.
4. Determine all nodes in the graph, which are located within the points d and R.
5. For all nodes N that fit this parameter:

Rapidly Exploring Randomized Trees Algorithm

Sometimes you need to build a path without applying previous scheduling requests. In such situations, the following method is required:

Create T Tree Empty.
Add to T the initial configuration of the robot.
Until the moment the goal is reached:
1. Sample for node R.
2. Determine in T the node closest to R. Give him the name K.
3. Move the robot from K to R until the following condition is met:
  1. In case of collision, proceed to the definition of a random sample.
  2. Otherwise: add a new node to the T in this configuration.
  3. If the maximum distance between d and K is reached, start working again on a random sample.
The solution is obtained if the chain node is located within the distance d from any node T.

Conclusion

For us, it is optimal to divide the issue of building a route into global and local. The global route is a list of target points for bypassing the field or the goal of returning to the base. The local route starts being built when an ultrasonic sensor or bumper has detected an obstacle.

Since in our specifics all obstacles have a convex shape, we use the simplest BUG algorithm, and even simpler. Some "patsansky" method of navigation. When an ultrasound detects an obstacle, the rover turns clockwise by 90 degrees, travels 1 m, turns 90 counter-clockwise. When an obstacle is detected, the bumper moves back 0.5 meters before turning.

Plans

During the start of the project in the summer of 2018. a lot of things happened. We are preparing a post about the development of our project. Thanks for attention!

Links

Source: https://habr.com/ru/post/426693/

All Articles