Satish Pedduri* K. Madhava Krishna*
Kinematically consistent paths for multiple mobile robots that are collision free for the next T steps are generated by forming collision free polygons (CFP). The polygons can be generated in a distributive fashion for each robot. All paths inside CFP that are kinematically feasible for a certain robot are collision free with all other robots in the same collision cluster for the next T time samples and with any other robot in the workspace in general. The construction of CFP is through two log-linear complex operations. The first one involves computing the intersection of the path container polygon (PCP) of a robot with PCP of other robots in the cluster. The second involves computing the convex hull of intersecting points arising from the intersection of PCPs. Once CFP is computed for a robot it chooses a point within the CFP (its next waypoint) that minimizes a cost function and moves towards the point. The process is repeated till the goal is reached. The main advantage of this method is that the best and worst-case times for finding a T-step ahead collision free path is always log-linear. In many randomized search methods, finding the paths till the next waypoint results in a worst case complexity exponential in number of robots. The efficacy of the current method is well portrayed through simulations. Comparative results show that the following method finds a collision free path to next way point much quicker.