Firebots: Autonomous Fire Detecting Robots

Navigation

Wavefront is a relatively simple yet very powerful global path planning technique. As mentioned earlier, it uses the unique approach of starting from the goal position and working towards the start position in order to determine the optimal path. Initially, the given map of the environment is discretized into a grid of uniformly sized squares. All obstacles in the environment are identified and marked as occupied accordingly. Each square is then assigned a cost value according to its position relative to the goal square. Squares closer to the goal receive lower values and increase with distance away from the goal so that the grid will consist of many linearly strengthening virtual force fields around the goal square. The optimal path from the start node to the goal node is the lowest cost path or the path of least resistance. Additional logic can be added to this algorithm in order make it more intelligent. For example, increasing the cost values to squares near the obstacles will increase path smoothness and reduce the chance of undesired collisions.

The VFH algorithm has been iteratively improving over many years now. The original approach was called Vector Force Field (VFF) and was quite possibly the first algorithm that offered smooth, high-speed trajectories without requiring the robot to stop. [11]





 



Cells which do not associate with an obstacle or the target have a force of zero. The sum of the forces R (Ftarget - Frepulsive) causes a change in the direction and speed of the robot in order to smoothly move around obstacles and towards the target. Although VFF was revolutionary at the time of its proposal, it suffered from several problems including operation in narrow hallways. The forces applied by either side of the hall would cause an unstable oscillatory motion which resulted in collision. The algorithm behaved undesirably in other situations such as those where two obstacles were very together and directly in front of goal. [11] her side of the hall would cause an unstable oscillatory motion which resulted in collision. The algorithm behaved undesirably in other situations such as those where two obstacles were very together and directly in front of goal. [11]

This polar histogram creates a probability distribution for each sector (of angular width α) based on the density of obstacles and several other factors. This normalization fixes the majority of the problems observed in the VFF algorithm. Vector forces are no longer applied in a single line of action; instead, numerous blobs of varying strengths push/pull the robot towards a general direction. Additionally, a reduction in the amount of data leads to an increase in efficiency in comparison to the VFF algorithm. [11] Although the wavefront and VFH algorithms each have the capability to reach the goal from the start position individually, this will not necessarily guarantee path optimality. VFH guarantees local but not global path optimality while wavefront does not perform real-time obstacle avoidance. This design will involve the implementation of a wrapper program in the central control system which will systematically assign goal positions to the wavefront driver in order to cover the given area in its entirety. The wavefront driver finds the optimal path from the robot’s current position to the given goal. It then forward smaller goal positions along the optimal path to the VFH driver in a sequential manner. VFH will in turn perform real-time obstacle avoidance and drive the robot to goal positions supplied by wavefront.

The combination of wavefront and VHF algorithms will offer a highly optimized hybrid methodology which will provide efficient and rapid navigation of complex environments while smoothly avoiding obstacles as well as guaranteeing local and global path optimality. This solution should meet and in fact exceed all required navigation objectives mentioned in the previous section.