Masters of Engineering Final Project

For practical robots optimal path finding or path planning are bound by its available resources. The kΩ (k‐omega) search optimization provides the power and versatility or various search algorithms that can be used to provide optimal solutions at the cheapest cost. In this research kΩ search algorithm was developed based on the A* algorithm to find an optimal path on a predefined grid. The kΩ optimization generalized the A* algorithm such that A* become a specific case of the kΩ algorithm. This new algorithm directs the resources to be specified through various parameters such that, instead of an absolute optimal solution, it allows for the resources to be predefined resulting in best answer possible with given constraints.  A simulation was developed to understand the various performance statistics for the algorithm with single and multiple agents. A collaborative flocking scheme allowed for multiple agents to use kΩ as a path planning and path finding tool.

For practical experimentation the algorithm was then used on the LEGO NXT robotics platform. The implementation shows how such at algorithm can be applied in real world application. A combination of laptop computers with Bluetooth technology were used to control the robots. The agents used kΩ algorithm to follow a leader robot on a grid.

[Project Proposal]   [Project Report]    [Source Code]