|
Procedures of the project
- The overhead camera captures images, then the function ˇ°process()ˇ± of ˇ°imageprocessˇ± class in Qt begins to process image;
- Transfer the image from RGB color space to HSV color space, and using predefined color to segment image and identify start point, walls and target in the image;
- Divide image into 7 X 10 grids, and change pixel positions of the start point, walls and target into grid position;
- There is an array called ˇ°map[7][10]ˇ± in the imageprocss class. It is used to store map information, 0 value in the array means the correspondent grid is walkable; 1 value means the grid is the start point; 2 value means the grid is the wall; 3 value means the grid is the target;
- After each element of the map array has been assigned the value, this array is used to generate an object of AstarFinder class (this class is programmed according to A star pathfinding algorithm);
- If AstarFinder can find a path from the start point to the target, it will return a nonzero path length;
- We created a string to store the path, the first element of the string is the path length, then we append each grid position of the path in sequence, such as x1,y1,x2,y2ˇ;
- In imageprocess class, it emit a ˇ°sendpathˇ± signal which will active slot ˇ°sendpathˇ± of qtcomm class to send out path string via serial port to the robot;
- When the robot receives the string, user_UARTFuncs.c reads the first element to check how long is the path, and assigns this value to variable TARGET_PTS. Which indicates how many grids the robot need to pass;
- Then the robot read each coordinate value from the string and assign to two arrays:targets_x[] and targets_y[];
- Finally, the robot uses xy_control mode to finish walking through the path.
|
|
|
A* PathFinding Algorithm
1) Add the starting square (or node) to the open list.
2) Repeat the following:
a) Look for the lowest F cost(see following definition) square on the open list. We refer to this as the current square.
b) Switch it to the closed list.
c) For each of the 8 squares adjacent to this current square ˇ
- If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.
- If it isn't on the open list, add it to the open list. Make the current square the parent of this square. Record the F, G, and H costs of the square.
- If it is on the open list already, check to see if this path to that square is better, using G cost as the measure. A lower G cost means that this is a better path. If so, change the parent of the square to the current square, and recalculate the G and F scores of the square. If you are keeping your open list sorted by F score, you may need to resort the list to account for the change.
d) Stop when you:
- Add the target square to the closed list, in which case the path has been found (see note below), or
- Fail to find the target square, and the open list is empty. In this case, there is no path.
3) Save the path. Working backwards from the target square, go from each square to its parent square until you reach the starting square. That is your path.
For more detail discription of the algorithm, please refer to: http://www.policyalmanac.org/games/aStarTutorial.htm
|
|
|
|
The key to determining which squares to use when figuring out the path is the following equation: F = G + H where
- G = the movement cost to move from the starting point A to a given square on the grid, following the path generated to get there.
- H = the estimated movement cost to move from that given square on the grid to the final destination, point B. This is often referred to as the heuristic, which can be a bit confusing. The reason why it is called that is because it is a guess. We really don't know the actual distance until we find the path, because all sorts of things can be in the way (walls, water, etc.). You are given one way to calculate H in this tutorial, but there are many others that you can find in other articles on the web.
|
|
|