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 f rom a starring 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 obsta cles. The robot has a sensing device that detects all obstacles or pie ces of wails lying beyond a fixed view range. A discrete version of th e problem is solved by an iterative algorithm that at any iteration st ep finds the smallest path length from the actual point to the target with respect to the actual knowledge about the obstacles, then the rob ot is steered along the path until a new obstacle point interfering wi th the path is found, at this point a new iteration is started. Such a n algorithm stops in a number of steps depending on the geometry, find ing a solution for the problem or detecting that the problem is unfeas ible. Since the algorithm must be applied on line, the effectiveness o f the method depends strongly on the efficiency of the optimization st ep. 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, tha t 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 wh en the problem is feasible or detecting the infeasibility condition ot herwise. Moreover the worst case computational complexity of the whole algorithm is shown to be polynomial in the number of nodes of the dis cretization grid. Finally numerical examples are reported in order to show the effectiveness of this technique.