Attention Makers


Any-Time Dynamic Path Planning Using Energy-Potential Gradient Ascent

MAKERS: Arka , Suhit COUNTRY: India

First, each grid in the maze is given an unique energy potential value. Energy-potential gradient of each cell always points to the destination cell and uses max gradient ascent algorithm.

The Purpose

-Transportation (GPS implementation, Public Transportation Route determination etc) -Autonomous car -Shortest route finding in Static, Dynamic environment and a combination of both (Urban Environment, shortest route to reach place of accident) -Military Purposes -Deep sea, Mine, Space Exploration purposes -Game Development -Robotics and Artificial intelligence

The Technology

Each grid in the maze (1s=traversable path; 0s=obstacles) is given an energy-potential value:- 1) the destination point is given a value of 1. Then each surrounding cell gets its energy value using the formula Eprescell=Eparcell/e^d. Eprescell=Energy of presentcell; Eparcell=Energy of parentcell; e^d= exponential of euclidean-distance(d); d=1 for straight grids, sqrt(2)=1.414 for diagonal grids (pythagoras-theorem). This algorithm is iterated until all grids except those with obstacles get unique energy-potential values. After each iteration, obstacle positions and destinationpoint can be changed. The robot recalculates the optimum path from it present position again and then climbs to the endpoint using maximum gradient route.

Additional Details

-Easy algorithm which can be implemented in any platform -Advanced path planning and superior to common Dijkstra's, A* and D* algorithms. -Reusability is an important feature. Once the maze is given the energy-potential surface, it can be used repeatedly with different starting points. -Very fast processing of large mazes. -Has major applications in many fields. -Robust as it can handle all types of mazes [static and dynamic- obstacles changing position, appearance of new obstacles, disappearance of old ones and change of destination cell]

Home Previous Next

Vote Share Comment