The Auction Technique for the Sensor Based Navigation Planning of an Autonomous Mobile Robot

The problem of finding a path for the motion of a small mobile robot from a starting point to a fixed target in a two dimensional domain is considered in the presence of arbitrary shaped obstacles. No a priori information is known in advance about the geometry and the dimensions of the workspace nor about the number, extension and location of obstacles. The robot has a sensing device that detects all obstacles or pieces of walls lying beyond a fixed view range. A discrete version of the problem is solved by an iterative algorithm that at any iteration step finds the smallest path length from the actual point to the target with respect to the actual knowledge about the obstacles, then the robot is steered along the path until a new obstacle point interfering with the path is found, at this point a new iteration is started. Such an algorithm stops in a number of steps depending on the geometry, finding a solution for the problem or detecting that the problem is unfeasible. Since the algorithm must be applied on line, the effectiveness of the method depends strongly on the efficiency of the optimization step. The use of the Auction method speeds up this step greatly both for the intrinsic properties of this method and because we fully exploit a property relating two successive optimizations, proved on paper, that in practical instances enables the mean computational cost requested by the optimization step to be greatly reduced. It is proved that the algorithm converges in a finite number of steps finding a solution when the problem is feasible or detecting the infeasibility condition otherwise. Moreover the worst case computational complexity of the whole algorithm is shown to be polynomial in the number of nodes of the discretization grid. Finally numerical examples are reported in order to show the effectiveness of this technique.