Uncategorized

A-Star Algorithms for Guided Search

A Comparative Study of A-Star Algorithms for Search and Rescue in a Perfect Maze focuses on using robots to find and rescue people in dangerous situations. There are many different situations where a robot may be the best answer to completing search and rescue missions. There could be a catastrophic earthquake or tornado where there is debris everywhere. There could also be flooding or damage due to hurricanes that force rescue missions on boat, like the recent flooding in South Carolina. The best way to put the ideas in this paper to use would be in a mining accident. Using an A* algorithm a robot can be programmed to search a disaster area to find victims who may be trapped within.

In a mining accident, there a many paths underground that could be blocked or inaccessible. An underground maze is created. There are also time limits due to the amounts of oxygen that are available to the mine workers. Growing up in a coal mining town in rural Pennsylvania, I have a lot of friends and family members who work in the mines. Even with the technology available today, it is still a very dangerous job that requires actual human workers to complete the actually mining. Until a fully functional robot is available for use, mining will still be completed by humans.

A few years ago, a large mining disaster occurred in West Virginia. There was a large explosion that closed off tunnels and trapped workers. As stated in the paper, a robot or even man controlled rescue vehicle can run through an algorithm to create a plan to search through the tunnels for an accessible route to the victims. A robot itself can have the algorithm embedded and set loose throughout the tunnels until it encounters the victims. Some parts of the mine many only have one entrance way into the farthest depths of the tunnel. To get to these depths, there can be many different pathways to reach the entrance of that depth. In the case of an explosion, there can be multiple blockages throughout the tunnel that create a maze-like environment underground.

A robot can be sent in first. It can travel through the mine using the algorithm as it traverses the tunnel and backtrack if it encounters blockages. This robot can be sent immediately after an explosion or accident is reported. Even though there are always rescue teams on site, they still take time to respond to an incident. Think of the response time much like the response time of an ambulance or fire truck. There are still preparations and precautions that need to take place before a rescue team can take over. This is the perfect scenario for a robot.

Since the robot was sent in immediately, it will already have checked parts of the mine to make sure that access is available to the rescue squad. This robot can also report back any situations via pictures or video that may be unexpected for the team. An example of this would be tunnel flooding. By sending a robot first, the flooding from the example can be identified and alerted to the team so that they can be equipped to handle the water.

The basis of the paper focuses on making the robot the one that the algorithm is built for. The algorithm should have the robot search through the parts of the mine as fast as possible. It can even be given a typical ending point based on a signal, the paper gives the example of miners tapping on a pipe to signal their location. This can be added into the algorithm for the robot so that it can change its search based on the information.

The robot would never be executing a blind search as there would always be a reason to send the robot in. The signal could come from actual miners or from electronic warning signals such as fume levels in the tunnel. A robot could then be equipped with special testing materials, like an air tester to test for chemicals in the tunnel itself.

Since the actual destination of the victim may vary based on movement and the accuracy of the signal, there will be deviation in the A* algorithm to make the changes to the final destination. This gives the robot a better chance at finding the victim in a search and rescue mission as there will always be issues that are unaccounted for. The main purpose of the algorithm is to find the shortest path to the victim and leave the disaster area.

The A* algorithm being discussed in the paper for the search and rescue missions is a search algorithm. To start the algorithm there is an input for the current position of the robot. This tells the position of the robot and can change based on the movement of the robot. This is similar to many other search algorithms. There is a starting point and some type of endpoint. The endpoint is the destination where the search will lead. There has to be some type of goal in mind before a search can take place.

Once you have a start point and an end point, the search can begin. One type of search algorithm is the Dijkstra’s algorithm. This is used a lot in networking when looking for the fastest connection time between a server and a computer. This algorithm finds the shortest path by visiting every node on a tree and calculating the time it takes to make a decision. Once it finds the shortest node, it then travels to that one and repeats again. This type of search is guaranteed to find the shortest path because it is an exhaustive search. It looks for all possible paths and scenarios while making its decisions. This is not optimal in a search and rescue because there might not be enough time to make it through all of the possible routes while moving through a maze.

A way to increase the success of a potential search and rescue is to have the search behave more like a human. This can be accomplished by adding features and controls to the robot. A sonar device like a bat would be used to detect distance and cut down on time searching for actual walls or road blocks. This can also be combined with a video camera and a flashlight to help detect any features along the course of movement for the robot. The more sensors that the robot has, the easier it will be to detect hazards along its course. It could also include safety features like carbon monoxide or other harmful gas detectors being onboard the robot. If it detects hazardous materials, it can send a relay message back to the home base so that they are aware of any risks of sending humans in to search.

Ideally the robot should behave rationally. If it senses harmful gases in one location or path, it needs to avoid that path during the rescue phase of its mission. This is important because if there is a successful rescue, the victim of the disaster will want to follow the robot out of the disaster area. The victim does not want to follow the robot into a potentially dangerous area that could pose another potential threat.

A maze would be more of a directed graph than a tree. There are many different directions that one can travel instead of just moving down into the next area. The robot will have to go through a maze of different routes and move around certain hazards. Knowing this, we will want the robot to move towards a goal driven search. The goal is the area where the disaster occurred. The robot will search along the path until it is able to reach that goal. Think of it like a mouse in a maze looking for cheese. The mouse will move along the course until it is able to find the cheese. That is the goal of the robot in a search and rescue mission.

We learned about two different types of searching, breadth-first and depth-first searching. Since this is a goal driven search where we are trying to reach our goal in the shortest time possible we would want to use a depth-first search. A breadth-first search is where the robot would search left and right and move across before moving down a level. This might work in a recovery robot or in a non-life threatening event where recovery is the most important. Think of a search where someone is looking for a dead body. The recovery of the body would be the most important thing. So a robot performing a breadth-first search going back and forth across a field would be an appropriate search algorithm. Since I have been using a coal mining example, we would want to go with a depth-first search. Since we have a general idea where the disaster has occurred, we want the robot to get as deep into the mine as quickly as possible.

Now depending on the scenario, this could end up being a blind search. If it is a focused robot, one owned by a mining company, they might be able to program a map of their mine into the robot’s algorithm. This would increase the speed of the search as the robot would have an idea of the possible direction that it would need to take. Think of using a GPS system in your car. The GPS system already has all of the roads programmed into it. If you hit traffic or construction, the GPS system is able to reroute itself around the hazard to reach its destination. This is the same behavior we need from the robot.

Now if there is a large area that needs to be searched, it may be beneficial to reduce that area into smaller chunks for the robot to encounter. This would be beneficial in the case of a very traumatic event. Let us say an earthquake or explosion caves in multiple areas of a large mine. We might receive signals from multiple areas inside of the mine but a majority of them are blocked off. It might then be beneficial to take a heuristic approach by tackling small parts of the mine at a time. Since the robot may have to perform backtracking more frequently in this scenario, it would be better to have small checkpoints along the way, sort of like nodes along a network path.

The paper builds off of these points and uses a heuristic, depth-first approach to programming a search and rescue robot. From the class slides, the “A* algorithm uses actual and heuristic values to compute an optimal solution.” This is ideal because the goal is never overestimated and it is built by being admissible. With it built on being admissible, a solution will most likely be optimal. There are a few disadvantages to this approach as a search of a large size can take quite a bit of processing power and memory. If a search and rescue robot also has a lot of bells and whistles built-in, it decreases the amount of processing power and memory for the search. This might not be a problem if there is a known list of routes, but it can be when there are a lot of unknowns in the search itself.

To make things seem even worse, the performance of the search is connected to the estimates that are being made. If an explosion is detected on one route of a mine, it can be programmed into the algorithm. But what if this explosion creates three other disconnected blockages? The robot might create an idea route but have another unknown blockage derail its search. Then it will have to reprogram the route which brings up the memory and processing power issue again.

Once the robot is on the trail, it will have even more limited resources at its disposal. Since the robot is being used to travel through disasters, it will have to run on battery power. Large processing power can eat through a battery very quickly. Try streaming a movie to your phone and compare the power usage of that to using it to send text messages. The streaming will eat through the battery much quicker as it is using the graphics processing power.

The basis of the search itself if f = g + h where g is the start point and h is the heuristic distance to the destination. The f is the actual time it takes to arrive at the destination. The paper adds a letter i to the search to make it a little more complex than the basic A* algorithm. The i is the current position of the robot. This is a key feature to add because the robot has to move throughout the maze in a disaster where unknown circumstances may cause the robot to have to reroute its course.

The paper then breaks down three differently programmed algorithms. This is highly beneficial because it shows a wide range of different outcomes. The surprise here is that the A* (2) algorithm always performed better. Sometimes the outcomes were very close but other times there was quite a bit of difference in the actual performance. In conclusion, the algorithm that adds a father node helps decrease the actual search time of the algorithm. This is very important in a search and rescue algorithm as it helps decrease response time in an emergency. Sometimes this can have a limited overall effect in efficiency, but other times it can make a huge difference.

The A* algorithm looks at a map and then makes decisions based on the surroundings and the perceived notion of where the goal is. Let us continue with our coal mining example. Let us say that the entrance is in the front of the mine. From there, the mine splits off into two separate directions. There are a few walls and obstacles that are in the way of the mine itself. The major mining for the mine is occurring in the bottom right side of the mine. There is a little alcove there where the mining accident occurs.

There is a cave-in at the mine right in the center where the path that the miners usually travel to the alcove gets blocked. The robot then has to start its search to find the path to the trapped miners. The miners are able to send a signal out from their location so that the rescue team knows that they are located in the alcove.

By known association, the robot begins to search on the right side of the breakaway entrance of the mine. As it moves around the mine itself it notices that the cave-in is in the center of the normally traveled path. Knowing the other location on the side, it is able to see that by going the opposite direction, to the left and down, it will be able to find another way into the recovery zone at the alcove. There is another wall that creates a boundary on the left side but the robot is able to cut above it so that it can then go straight down into the alcove. There is a path to the right of the alcove but the robot does not even check there as there is no need to go around the long side to see if it can get through. There is already a path created.

There is another known path to the alcove, one where the robot could have gone straight down to the left and then over, but it already had an idea that the trapped miners were on the right side of the mine based on their alert. So as soon as the robot had an opening, it cut back to the right towards the location of the trapped miners. This is the brilliance of the A* algorithm. It knows the miners are on the right side of the mine so it continues to work its way to the right side of the mine. Even though, at the start, the right side ended up being blocked from the robot.

I created a graphical representation of the mine itself. There are two variations. The first variation is when the mine is actually blocked. The robot itself would have to check a lot more of the area before finding access to the victims. The second variation is the actual mine without blockage in the area that the miners normally travel to.

The miners are working and hear the explosion. They walk up the right side of the alcove to check and see what has happened. They see that their path is blocked. The mine is very dark and hard to see, so they head back to their alcove to signal for help. The entrance of the mine is at the very top and is marked by a star. I used a green marker to represent the actual walls of the mine. The mine walls are actually very narrow so the team does not have a lot of room to move around. I have marked their location as the end with another star. They are located in the bottom right side of the drawing. The blockage I have colored in a circle with a black pen and labeled off of the map as blockage. The second map has the same layout without the blockage shown.

On both of the maps, I have the shaded in the searched areas with a blue pen. The path that the robot would end up taking is colored in red pen. The closer the blue to the red pen, the closer the nodes are to the actual path that has been taken. The blue area also corresponds with the amount of time that it takes the robot to actually perform the search. The more ground that the robot covers, the more time it takes the robot to perform the search. On the first map, the robot looks to the right since it knows the alcove is on the right. There is no open path as that is where the blockage has occurred. The whole right side is shaded right as that is the direction that the robot wanted to move. It knew that it had to move right but it was not able to find an opening.

Once the right side had been searched, the robot moves to the left side of the split trail. From there it also moves right and comes back in contact with its path from the previous search. So now, all areas around the path have been shaded blue. The robot now starts to work its way down as it moves to the right. The left sides are checked but the robot continues on its path down and to the right. There is an opening there so that is the direction in which the robot moves. The lower right side of the map would not be searched and that is ignored. That is because the robot worked up and under the left side of the alcove. Looking at the map, it would appear that over 75% of the mine has been checked by the robot.

On the next map, the blockage has not happened. The robot moves to the right as it tried to do before. It works its way to the right and starts to move down. There is no blockage so the robot continues to work down and to the right. As it comes down to the right side of the alcove it knows that there is no blockage and that the entire path is open. It continues straight down the right side of the alcove until it can turn up to where the victims would be located. The left side of the map is left unshaded as that side has not been checked by the robot. Looking at this map less than 50% of the map has been checked by the robot before it has reached its destination.

In conclusion, an efficient algorithm can be made inefficient due to unforeseen circumstances that could occur on a search and rescue mission. There are a variety of factors that could make a search and rescue a success. Ideally, the less ground that is searched for a route, the more efficient and success the route will be. That is why Dijkstra’s algorithm or a similar one is not advocated in the paper.

Drawing of the mining example to show the blockage and correct route

The A* algorithm is an algorithm that has far reaching uses. The focus of the second paper I chose was using the A* algorithm for search and rescue missions. Chunbao Wang, Lin Wang, and Jian Qin from Sun Yat-sen University along with Zhengzhi Wu, Lihong Duan, Zhongqiu Li Mequn Cao, and Xicui Ou from the Shenzhen Institute of Geriatrics focus their paper, Path Planning of Automated Guided Vehicles Based on Improved A-Star Algorithm, on using the algorithm to improve the routes of guided vehicles. The papers have the same type of premise, as they are both looking to have guided machines use the A* algorithm to generate a route for a machine to take.

The improved A* algorithm proposed in the Automated Guided Vehicles could very easily be applied to the rescue robot. The goal of the improved algorithm reduces turning and removes edges from the route so that a more direct route is taken. This is included in the vehicle algorithm because with the lower amount of turning a vehicle does, the less chance there is of an accident occurring. The longer route a vehicle takes, the greater chance of an accident occurring also is true. The longer a vehicle is moving the more dangerous the route becomes. That is the purpose of finding the fastest route.

The purpose of finding the fastest route in a search and rescue mission is to save as many lives as possible. Looking at both papers, safety is the reason behind using the A* algorithm to guide the machines through a maze of directions. Both also have to take into account that the environment might end up changing after the initial route is chosen. There may be environmental issues such as blockages or hazards that interfere with the actual route. In the case of the robot, it could get stuck and not be able to complete its mission. For the vehicle, it could cause an accident and potential harm to people.

Time is also important in both papers. For the search and rescue, this is of upmost importance because the longer it takes the robot to arrive at the destination, the greater the chance of an increased loss of life could occur. For a guided vehicle to be practical, it also has to make quick route decisions and be able to arrive in a timely matter. This goes along with the safety of both the guided robot and the vehicle. Safety is important, but so is the amount of time it takes for the robot and vehicle to arrive at their destination. One could argue that time is more important to the robot and safety is more important to the vehicle, but in reality they are required by both.

The difference between the two papers is in the application of the actual A* algorithm. The goal of the guided vehicle is to decrease the number of turns that it is has to take to reach the destination. When looking at the comparison of actual shortest path and the basic A* algorithm, they are getting the same performance speed-wise from all of them. The path length for all three improved A* algorithms, the Dijkstra, and the A* all traveled a length of 45 nodes. The Dijkstra traveled all 32 nodes to reach its route conclusion. This added extra time to its route configuration while all of the A* were right around the same amount of nodes search. The improved A* routes did shave off a few nodes from the original A* algorithm.

These results look good and all, but they were only configured on one map. I liked the fact that the search and rescue paper included multiple mazes with speed breakdowns of each. It was clear from that paper that the A* (2) algorithm was the best algorithm to be used in a search and rescue scenario. One could draw similar conclusions on the improved A* algorithms, but there is not an overall sufficient body of work to draw that conclusion.

Another difference between the two situations is the collision feature. In a search and rescue, there will not be a bunch of other robots traveling in different directions and having different goals. The robots will be focused on the same goal of rescue. In the guided vehicles paper, the goal would be to have self-sufficient vehicles on the road. In a large scale production, a self-guided vehicle would have to be able to maneuver throughout highway traffic. The algorithm has a built in time collision detector that would avoid conflict. If a conflict can be avoided by waiting, then the vehicle waits.

Think of this in a real world situation. A car is being driven down the road and two pedestrians walk across a crosswalk. The car cannot run over the pedestrians. The guided car would have to make adjustments. With a wait time implemented, the guided vehicle would take time to make sure that the crosswalk is clear and then it would proceed across. For this to be effective, there would have to be very sensitive sensors built into the car. The car would have to be able to detect walking people or animals in a split second.

If a deer or other animal jumped out in front of the vehicle, it would have to make a quick decision to avoid the collision. It could still implement the wait time, but it would have to be signaled to the vehicle quickly. This sensor would have to be able to tell the difference between an actual collision and not a perceived one. What if there was a heavy rain outside that immediately started around the car? Would the car pick up the motion of the rain and calculate that as a possible collision? It would be pretty silly for a vehicle to stop as soon as it started to rain or even snow. There are quite a few different situations where these features would have to be tested extensively before they are road ready.

In a search and rescue environment, the robot does not have to worry about oncoming collisions and unexpected objects like a vehicle would. Sure, there might be falling debris in a mine after an explosion, but a disaster area would be more of an isolated environment when compared to the guided vehicle. The guided vehicle would have a more controlled environment when compared to the robot as well. The vehicle will always have at least a minimum width of road and stable surface to drive on, while a robot may not have either in its working environment.

When looking at the algorithms used by both, they are very similar. Since both are using an A* searching algorithm the results are going to be consistent across both uses. The vehicles tried using a Dijkstra algorithm for comparison while the search and rescue did not. It did not make sense for the search and rescue to use that algorithm because there would never be a scenario where every location would be visited when time is of the essence. The guided vehicle used an improved A* algorithm while it was clear from the simulations that the best A* algorithm used by the search and rescue was the A* (2) algorithm.

The A* (2) algorithm is “f2(i) = g2(i) + h2(i) + h2(j).” In this algorithm, the f is the course that the node will take. The i used throughout is the location of the robot in the search. The g is the start point and the h is the end point that is being estimated. The j then used, is the father point along with the estimation. The father point improves the search speed. It does this because there are less nodes for the search to look through while it determines its path. Since we are going depth first, the father node helps create a sort of tree even though we are using an undirected graph. We do not want to backtrack or spread out, so this point helps create an increase in speed which is why we see it run faster than the other A* algorithms in the simulation.

This might help increase the speed of the car, but I do not think it is necessary. In the guided vehicle, the destination is the goal with the least amount of turns. A much simpler algorithm can help achieve this goal without coming across the extra processing power needed to traverse a more directed graph with another node to consider. The vehicle algorithm initialized the i value to 1 and works through the shortest path. It also takes into account comparisons between the goal location and the estimated distance. This is something that doesn’t need to occur in the search and rescue because it is not trying to limit moves like the car is trying to limit turns.

Overall, both papers use a similar idea to solve a very similar goal. The slight differences in the overall scope of each project leads to different algorithm outcomes even though both are based on the A* search algorithm.

References

  • Farmer, Michael. CSC546 — Artificial Intelligence: Classroom Slides. 2015.
  • Liu, Xiang. A Comparative Study of A-star Algorithms for Search and rescue in Perfect Maze. 2011.
  • Wu, Zhengzhi. Path Planning of Automated Guided Vehicles Based on Improved A-Star Algorithm*. 2015.

Leave a Reply

Your email address will not be published. Required fields are marked *