Multidimensional online mobile robot planning

Josh Brown Kramer Address: Mathematical Sciences Illinois Wesleyan U Bloomington, IL 61701 Office Phone: (309) 556-3146 Email: jbrownkr@iwu.edu

Lucas Sabalka Address: Mathematical Sciences Binghamton U, SUNY Binghamton, NY 13902-6000 Office Phone: (607) 777-4246 Email: sabalka@math.binghamton.edu

Results

We consider three related problems of robot movement in arbitrary dimensions: coverage, search, and navigation. For each problem, a spherical robot is asked to accomplish a motion-related task in an unknown environment whose geometry is learned by the robot during navigation. The robot is assumed to have tactile and global positioning sensors. We view these problems from the perspective of (non-linear) competitiveness as defined by Gabriely and Rimon. We first show that in 3 dimensions and higher, there is no upper bound on competitiveness: every online algorithm can do arbitrarily badly compared to the optimal. We then modify the problems by assuming a fixed clearance parameter. We are able to give optimally competitive algorithms under this assumption.

Code

We have implemented portions of the algorithms described in the paper Multidimensional online mobile robot planning. Our implementations are for the NAV problem in 2 and 3 dimensions. We have used VPython for the implementations.

At this stage, our code is rough and preliminary. In particular, the code has a known problem when dealing with floating point error which can occasionally cause erratic behavior. Also, the implementation is not currently stand-alone, and so requires a VPython compiler. We will continue to improve and refine these implementations, including releasing a stand-alone version.

Click here to download Version .41.

See below for screen shots.

Screen Shots

• light and dark blue objects are obstacles
• green spheres are the start and target points
• the yellow sphere is the robot
• the cubes represent the robot's memory of its environment:
  • red cubes are too near an obstacle
  • yellow cubes have been visited
  • pink cubes are the virtual boundary (in 2D)