Planning plays a key role in any level of computation and problem solving. Given the problem statement and having decided on the goal, critical analysis and strong heuristics greatly impact the outcome of the action taken. While problem solving by default demands high precision and concentration, the level of uncertainty involved in the environment where the problem is solved is of significant importance. In this thesis we address the problem of traversing all the cells of a grid by a collection of cooperating robots. Several factors such as static/dynamic obstacles, nature of the terrain and natural factors elevate the uncertainty of the actual outcome. With the increasing amount of research into both static and dynamic environments, the challenges to be faced in the domain of collaborative robotics are still too many to enumerate. Several areas of artificial intelligence are still addressing these issues and this thesis addresses one problem for cooperating robots.
The primary goal of this thesis is to generate intelligent paths for a collection of robots in an environment with dynamically changing obstacles. Many existing approaches have addressed the problem in the context of a global camera or GPS system providing positional information to each robot. Our approach seeks to solve this problem in the context of robots getting their location information from a visible grid covering the terrain. The terrain is divided into a well-spaced grid and robots are challenged to visit every cell in the grid in the shortest period of time while overcoming starvation, avoiding deadlocks and detecting dynamic obstacles. All of their spatial knowledge is derived from the cell boundaries on the grid that they cross. This formulation with marked grid boundaries calculates paths, taking both global and local states of all the robots into consideration. Factors such as repeatedly visiting a cell, overlapping paths generated by two robots, and travel-time cost estimations are considered significant in calculating the most effective and intelligent path. The individual path generated by each robot is in response to the obstacles that were encountered during the executions of the path traversals.
The algorithm thus developed has been successfully tested with real robots in a laboratory setting. Robots with individual start points visited all the cells in the two dimensional grid. The overall execution time of the algorithm differed with the velocity, the nature of the terrain, and the relative start points. Interesting observations were made such as task sharing, resource utilization, and visiting the nearby cells rather than waiting for other robots to travel far in visiting those cells. The execution time was comparatively less when robots initiated with start points subjected to lower chances of starving, mutual exclusion, respecting better performing robots while avoiding accidents, and building global information from local information. The overall performance of the algorithm is analyzed and discussed in this thesis.