A framework for mobile robot concurrent path planning and execution in incomplete and uncer.pdf

To appear: AIPS-98 Workshop on Integrating Planning, Scheduling Execution in Dynamic Uncertain Environments 1A Framework for Mobile RobotConcurrent Path Planning Executionin Incomplete Uncertain EnvironmentsJohn S. ZelekEngineering Systems Computing,School of Engineering, University of Guelph,Guelph, ON, N1G 2W1, Canadae-mail: jzelek@uoguelph.cawww: 0/webles/zelek/AbstractSensor-based discovery path planning is problematicbecause the path needs to be continually recomputed asnew information is discovered. A process-based client-server approach is presented that permits concurrentsensor-based map and localization-correction updatesas well as concurrent path computation and execution.Laplaces equation is constantly solved (i.e., a harmonicfunction) by using an iteration kernel convolved withan occupancy-grid representation of the current freespace. The path produced (i.e., by steepest gradientdescent on the harmonic function) is optimal in thesense of minimizing the distance to the goal as well asa hitting probability. This helps alleviate the in uenceof uncertainty on path planning. An initial heuristicestimate provides the path planner with instantaneousresponse (i.e., reactive), but with some deliberation it isable to produce optimal paths. In addition, the compu-tation time for generating the path is insignicant pro-vided that the harmonic function has converged. Ona regular grid, the computation of the harmonic func-tion is linear in the total number of grid elements. Aquad-tree representation is used to minimize the com-putation time by reducing the number of grid elementsand minimally representing large spaces void of obsta-cles and goals. IntroductionSensor-based discover path planning is the guidance ofan agent - a robot - without a complete a priori map,by discovering and negotiating with the environment soas to reach a goal location while avoiding all encoun-tered obstacles. A robot must not only be able to createand execute plans, but must be willin