Algorytmy czasu rzeczywistego do poszukiwania drogi w zastosowaniu praktycznym

Modern mobile robots can perform a variety of tasks spanning from simple movement to highly sophisticated environment map creation [1]. The overall performance is greatly influenced by the hardware installed. For that reason, engineers aim to develop CPUs with high processing power and low energy consumption, as well as high amount of memory available for storing program data. Such approach allows for creation of smaller and lighter constructions with longer operation time. Unfortunately, there is a limit of how much can be achieved with hardware alone. The importance of using the right software can be clearly seen in the time a robot needs to find the shortest available route between two points [2]. To this end, researchers are developing more efficient algorithms for finding the optimal path.

The main goal of the robot is to calculate the best way from the starting to the ending points with as low cost as possible. There are many path finding algorithms, each of them exhibiting different advantages and disadvantages. Among them there is the Lee’s algorithm [7], which is an application of the breadthfirst shortest path search algorithm. Unfortunately, it is highly inefficient because it requires vast amounts of memory and slows down with bigger maps. There are many variations of the original Lee’s algorithm [8]. Other algorithms that present good results are the fluid motion algorithm [9] and the motor schema based algorithm [10]. The first represents the approach of fluid’s reaction to obstacles, dynamically adjusting to the environment and the second combines multiple schemas into an efficient decision making pathfinder. Another algorithm that can be effective is called Ant Colony Optimization (ACO) [11]. It originated from observation of ants’ pathfinding abilities and is said to produce optimal path in finite time. The algorithm depends on the quality of solution from multiple simulation agents (artificial ants) thus it is an example of a parallel algorithm. It is possible to improve the computation speed of the algorithm by combining it with the minimum spanning tree (MST) which usually consists of 70-80% of the optimal path [12]. However. this is not the only swarm intelligence type algorithm. There is also the Particle Swarm Optimization (PSO) [12, 13] that assigns initial velocity values to particles and after certain amount of time performs evaluation of the results of their transition through the solution space. Then the particles tend to accelerate towards the ones with best fitness in their group. The last two mentioned algorithms are the Dijkstra’s algorithm [14, 15] and the A-Star algorithm [16-25]. They both represent the same start point computations but differ along the way.

The paper is organized as follows: creation of maps will be explained in Section II, A* algorithm will be briefly described in section III, Section IV explains the system architecture for a mobile robot. Section V discusses implementation of the Astar algorithm, the visual interface for a mobile robot. Section VI presents the experimental results with analysis. Section VII concludes the paper. 

Map creation

Although robot movement is an easy task, finding the optimal path can become a very complex problem [3]. Usually the dimensions in which a path is supposed to be found can be covered by position on a 2D graph. In accordance to that, the map can be considered an XY graph with each tile being a vertex.

Fig. 1. Basic topology of the map [4]

Figure 1 [4] presents a typical map, where obstacles are depicted as black color cells, starting point is a light gray color cell, and ending point is a dark gray cell. The robot that is going to move to target location does not know the topography of the surrounding environment [5]. Despite the fact that the information about topography is not available, it is possible to represent the land features by assigning a coefficient defining difficulty of covering the route from point A to B to each edge of a tile. Determining the coefficient enables to consider not only the slope, but also many more features, such as type of the ground [6] (Fig. 2).

Fig. 2. Map with cost of movement between tiles [4]

GOALS

The main goal of the object is to calculate the best way from the starting to the ending points with as low cost as possible. It is also interesting to check the possibility of application of the A-star algorithm which could be tested on the real mobile robot platform. Model of the mobile platform is described in Section IV. The robot is equipped only with a simple touch sensor, digital compass, and CMOS camera, and does not know anything about the layout of the map, which constitutes a major problem. It can only view its surrounding spaces and store them (it memorizes the surrounding tiles of every space it visits).

Prototype architecture

Figure 3 illustrates a block diagram of the basic components of the proposed systems, whereas the Figure 4 shows the prototype of robot platform for real-time search algorithms.

Fig. 3. Basic structure of the prototype

All elements are connected to acrylic glass base. Robot sees environment only by three HC-SR04 ultrasonic sensors. One of them is oriented forwards, the remaining two are faced on to the left and right side.

Fig. 4. Prototype of mobile platform for real-rime search algorithms

When the system starts, the first action performed by the robot is verifying distance to obstacles on each side and in the front by sending a trigger impulse to ultrasonic sensors. Measured distances are saved as three variables, and sent by a Bluetooth serial device. If the variables have been properly sent to the computer it receives signals and starts to calculate the next move using the A-star algorithm. In our case, the robot moves forward and backward and it is able to rotate left and right by ninety degrees.

Accuracy of movement is provided by an encoder on each motor. Upon finishing a movement, the robot sends the “ready” signal to the computer, and waits for another measurement request.

The process repeats until platform has reached the destination point.

A star implementation

The A* algorithm, which is a graph searching algorithm. has been designed to find the shortest path between two points called nodes. It has been developed by Peter hart, Nils Nilsson and Bertram Raphael in 1968. Compared to other similar algorithms, it is faster and more efficient because it finds an optimal path, calculating a smaller number of vertices of the graph. Through the use of heuristic functions for searching graph it first checks the most promising unexplored point.

The implementation of the algorithm is performed in several steps. At first, it is entered at the starting point A and added to the “Open List” field waiting to check It contains fields that may create a path, and need to be verified.

Searching all available fields to be marked as possible, adjacent to the starting point (point A), ignoring those with walls or other labeled as impossible. Add to the Open List. For each of these fields, point A behaves as a “parent field”. This activity is important due to the possibility of moving along the designated path.

The starting point A is removed from the Opened List and added to the Closed List in order to be checked so that it does not need to be verified again.

Each point has 4 neighbors, that have to be verified. In order to find the path (choose the best field) we shall apply the following equation:

F = G + H ⁽¹⁾

where: G – the past path cost function, which is the cost from starting node to current node, H – the future path cost function, which is a heuristic distance from current node to the goal.

In order to determine the path of the mobile robot some modification should be conducted. The modifications of the properties of the robot and the environment in which they occur are present in the following formula:

TotalCost = G + movingCost + rotationCost + H ⁽²⁾

In tests we have used four different types of heuristic function.

They are:

• Manhattan distance
• Diagonal distance

hX = d⋅max (|n.x − goal.x|, |n.y. − goal.y|) ⁽⁴⁾

• Euclidean distance:

hX = d⋅√(n.x − goal.x)² + (n.y.− goal.y)^{2 (5)}

• Euclidean distance squared:

hX = d⋅(n.x − goal.x)² + (n.y.− goal.y)^{2 (6)}

The vehicle is at first situated at the center of the virtual map, which depends on dimension of the map. It can move in four directions. The experimentally measured time needed to move equals 3 s, while rotation cost of the straight angle equals 3 s, and of the right angle equals 2 s.

Velocity has been chosen to compensate for slipping and object reflection from the wall.

Test Run

An application developed in C# was created to control the mobile robot. The robot is controlled using a Bluetooth communication, and itself it can only move straight, rotate and send measurement from sensors to a master application located in a computer. After connection the application begins in center of an unknown map and the application receives measurement from sensors in order to have basic information about nearest area. Three ultrasonic sensors were used to check/examine the space near the vehicle. Each sensor detects area near the robot and verifies if there is an obstacle. Threshold equal to the value of the virtual map field dimension was used to define an obstacle.

At first, we choose a destination point in the virtual map and the application calls astar function to calculate the best path using information from the environment. After each map update, astar calculates the path using new information from the nearest area.

If it detects an obstacle all information used by the astar function is erased and the astar function is recalled. It proceeds continuously in the same manner until the robot’s position is the goal position or destination is an obstacle. Figures 6–13 present some movements of the mobile robot platform and basic robot path map generator in test environment Figure 5.

Fig. 5. Draft of test run environment

Fig. 6. Predicted robot path without obstacles (blue point – current position, green point – the goal)

Fig. 7. Movement of prototype platform in the beginning of map generation

Fig. 8. Predicted robot path upon detecting an obstacle

Fig. 9. Movement of prototype platform upon detecting an obstacle

Fig. 10. Predicted robot path after avoiding detected obstacle

Fig. 11. Movement of prototype platform after avoiding detected obstacle

Fig. 12. Reaching the goal of simulation

Fig. 13. Prototype platform reaching the goal of test run

Fig. 14. Comparing results of test runs with different heuristics:
1) Euklides, 2) Euklides without sqrt, 3) Manhattan, 4) Diagonal

In this example, the goal is an obstacle and the algorithm stops working. Upon application of different heuristics, the test shows, that Euklides without square and Diagonal are the best heuristics for four directions of movement. Figure 14 depicts effects of using different heuristics.

It can be clearly noticed that the proposed solution is the best for our experiments.

Conclusions

This process seems to be an excellent solution for those who cannot place more expensive and more accurate sensors on their mobile robot. In future experiments we aim to improve process as a potential solution to other methods of mapping and navigation. This method uses little computational power, and its main downside would be that this process takes time. Each path, even if it is fairly short, would take at the least a few seconds to be analyzed.

The A-Star algorithm is in our opinion the best search algorithm that finds the least costly path from starting to ending points. Traditional real-time searches are Eulerian, and therefore cannot be used to distinguish between efficient and inefficient real-time search algorithms.

References:

[1] Elfes A.: “Sonar-based real-world mapping and navigation,” Robotics and Automation, IEEE Journal of , vol. 3, no. 3, pp. 249–265, June 1987.

[2] Avnaim F., Boissonnat J.D., Faverjon B.: “A practical exact motion planning algorithm for polygonal objects amidst polygonal obstacles,” Robotics and Automation, 1988. Proceedings., 1988 IEEE International Conference on , vol., no., pp. 1656–1661 vol. 3, 24–29 Apr 1988.

[3] Murphy R.: Introduction to AI robotics, “Navigation”, MIT Press, 2000

[4] Burdziuk A., Pochmara J., Lakomy K., Szablata P., Koppa R.: “Realtime physics engine for robots movement,” Mixed Design of Integrated Circuits and Systems (MIXDES), 2012 Proceedings of the 19th International Conference , vol., no., pp. 511–515, 24–26 May 2012

[5] Sheu P., Xue Q.: Intelligent robotic planning systems, Robot Path Planning, World Scientific Publishing Co., 1993.

[6] Cook G.: Mobile Robots: Navigation, Control and Remote Sensing Robot Navigation, John Wiley & Sons, Inc., 2011

[7] Lee C.Y.: “An Algorithm for Path Connections and Its Applications,” Electronic Computers, IRE Transactions on, vol. EC-10, no. 3, pp. 346–365, Sept. 1961.

[8] Akers, Sheldon B.: “A Modification of Lee’s Path Connection Algorithm,” Electronic Computers, IEEE Transactions on , vol. C-16, no. 1, pp. 97–98, Feb. 1967.

[9] Didier K., Jo D.: “A flexible path generator for a mobile robot,” Advanced Robotics, 1991. ‘Robots in Unstructured Environments’, 91 ICAR., Fifth International Conference on , vol., no., pp. 1069–1073 vol. 2, 19–22 June 1991.

[10] Arkin R.: “Motor schema based navigation for a mobile robot: An approach to programming by behavior,” Robotics and Automation. Proceedings. 1987 IEEE International Conference on, vol. 4, no., pp. 264–271, Mar 1987.

[11] Marco Dorigo, Vittorio Maniezzo, and Alberto Colomi, “The Ant.

[12] System: Optimization by a colony of cooperating agents”, IEEE Transactions on Systems, vol. 26, no. 1, pp. 1–13, 1996.

[13] Liu Wei, Zhou Yuren: “An Effective Hybrid Ant Colony Algorithm for Solving the Traveling Salesman Problem,” Intelligent Computation Technology and Automation (ICICTA ), 2010 International Conference on, vol. 1, no., pp. 497–500, 11–12 May 2010.

[14] Wen-liang Zhong, Jun Zhang, “A novel discrete particle swarm optimization to solve traveling salesman problem”, 2007 IEEE Congress on Evolutionary Computation (CEC 2007).

[15] Jasika N., Alispahic N., Elma A., Ilvana K., Elma L., Nosovic N.: “Dijkstra’s shortest path algorithm serial and parallel execution performance analysis,” MIPRO, 2012 Proceedings of the 35th International Convention, vol., no., pp. 1811–1815, 21–25 May 2012.

[16] Hwan Il Kang, Byunghee Lee, Kabil Kim: “Path Planning Algorithm Using the Particle Swarm Optimization and the Improved Dijkstra Algorithm,” Computational Intelligence and Industrial Application, 2008. PACIIA ‘08. Pacific-Asia Workshop on , vol. 2, no., pp. 1002–1004, 19–20 Dec. 2008.

[17] Hart P.E., Nilsson N.J., Raphael B.: “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” Systems Science and Cybernetics, IEEE Transactions on, vol. 4, no. 2, pp. 100–107, July 1968.

[18] G. Gordon S., Thrun M., Likhachev ARA*: Anytime A* with Provable Bounds on Sub-Optimality, pp. 8, School of Computer Science Carnegie Mellon University Pittsburgh.

[19] Trovato K.I.: “Differential A*: an adaptive search method illustrated with robot path planning for moving obstacles and goals, and an uncertain environment,” Tools for Artificial Intelligence, 1989. Architectures, Languages and Algorithms, IEEE International Workshop on, vol., no., pp. 624–639, 23–25 Oct 1989.

[20] DUAN Li-qiong, ZHU Jian-jun, WANG Qing-she, MA Ling. Fast Realization of the Improved A* Algorithm for Shortest Route. HYDROGRAPHIC SURVEYIN G AN D CHARTIN G. Vol. 24, No. 5. Sep, 2004, p. 20–22.

[21] Khantanapoka K., Chinnasarn K.: “Pathfinding of 2D & 3D game

[22] Real-time strategy with depth direction A* algorithm for multi-layer,” Natural Language Processing, 2009. SNLP ‘09. Eighth International Symposium on , vol., no., pp. 184–188, 20–22 Oct. 2009.

[23] Millington I., Funge J.: Artificial Intelligence for Games, 2.2.2 Heuristics, Evlsevier Morgan Kaufmann, Inc., 2009.

[24] Bourg D., Seemann G.: AI for game developers, A* Pathfinding, O’Reilly Media, Inc., 2004.

[25] Blaich M., Rosenfelder M., Schuster M., Bittel O., Reuter J.: “Fast grid based collision avoidance for vessels using A* search algorithm,” Methods and Models in Automation and Robotics (MMAR), 2012 17th International Conference on , vol., no., pp. 385–390, 27–30 Aug. 2012.

[26] Nordin N.A.M., Zaharudin Z.A., Maasar M.A., Nordin N.A.: “Finding shortest path of the ambulance routing: Interface of A* algorithm using C# programming,” Humanities, Science and Engineering Research (SHUSER), 2012 IEEE Symposium on , vol., no., pp. 1569–1573, 24–27 June 2012.

[27] Tournassoud P., Jehl O.: “Motion planning for a mobile robot with a kinematic constraint,” Robotics and Automation, 1988. Proceedings., 1988 IEEE International Conference on , vol., no., pp. 1785–1790 vol. 3, 24–29 Apr 1988.