10.1 Problem Setting
- Robot moves with 8-point connectivity.
- Target moves with 8-point connectivity.
- Both the robot and target can execute only one move at a time.
- The environment(2D) is unknown to the robot; the only known information is the position of the target.
10.2 Employ A*?
The first solution that anyone can think of: do a A\* search. But, there are some perks of target that we need to take into consideration: it can move i.e. goal changes; $g-values$ and $h-values$ of each node changes. Consequently, we need to continuously replan from scratch as the goal changes. Let's see how it performs:
Figure 10.1 Robot Catch Example 1
Pretty easy, right? Let’s take another environment:
Figure 10.2 Robot Catch Example 2
Here, we can see that the A* algorithm fails in such a simple looking environment. We know that A* needs to start from scratch if the goal changes. In Figure 10.2, the target is continuously moving, and the A* algorithm is not able to search enough to escape the L-shaped obstacle. One solution to this: block the location which has been explored more than twice in an oscillatory motion.
Figure 10.3 Robot Catch Example 3
10.3 Artificial Obstacles!
As said earlier, when a location is explored twice: we put an artifical obstacle on that location. Consequently, the A* algorithm won't visit the same node again and again. There are two steps to put an artificial obstacle:
- Detection of oscillation: to and fro motion
- Changing the node from free space to obstacle
Figure 10.4 Artificial Obstacle
10.4 Teleportation
Using the above method, the robot may sometimes find itself completely surrounded by obstacles (artificial and the original ones). In this case, the robot should ignore the target for a while and find the nearest free cell; further, it should run A* search to that free cell. During this A* search, the artificial obstacles are removed and placed back again as the search completes. Figure 10.5 clearly demonstrates this behaviour. Whenever this scenario is encountered by the robot; it implies that the robot has completely explored that area and needs to move out.
Figure 10.5 Surrounded by Obstacles
In this, it looks like the robot teleports through the artificial obstacles; that’s why the name is teleportation
</> GitHub
10.5 References
[1]. 16-350 Planning Techniques for Robotics - link
[2]. Choset H., Lynch K. M., Hutchinson S. Kantor G., Burgard W., Kavraki L. E., Thrun Sebastian. Principles of Robot Motion. MIT Press