An intelligent algorithm to generate non-intersecting paths for mobile robots in a multi-robot environment

A heuristic algorithm for generating nonintersecting paths for mobile robots in a multirobot environment with polygonal obstacles is presented. This problem is far more complex than the traditional problem of path planning among obstacles. Each robot is assigned a specific task and has a unique origin and destination. Search techniques are to be used to find the global optimum solution of minimum total distance of paths. The proposed approach consists of discretizing the space and using a two-stage heuristic strategy to reach the solution. The outer-level heuristic function works for a global optimum solution while the inner-level heuristic function determines the best path for a robot at a given state of configuration. The algorithm uses a matrix to keep it informed of the status of the environment as new paths are formed