Some Experimental Results in Multistrategy Navigation Planning

Abstract

Spatial navigation is a classical problem in AI. In the paper, we examine three specific hypotheses regarding multistrategy navigation planning in visually engineered physical spaces containing discrete pathways: (1) For Hybrid robots capable of both deliberative planning and situated action, qualitative representations of topological knowledge are sufficient for enabling effective spatial navigation; (2) For deliberative planning, the case-based strategy of plan reuse generates plans more efficiently than the model-based strategy of search without any loss in the quality of plans or problem-solving coverage; and (3) For the strategy of model-based search, the “principle of locality” provides a productive basis for partitioning and organizing topological knowledge. We describe the design of a multistrategy navigation planner called Router that provides an experimental testbed for evaluation the three hypotheses. We also describe the embodiment of Router on a mobile robot called Stimpy for testing the first hypothesis. Experiments with Stimpy indicate that this hypothesis apparently is valid for hybrid robots in visually engineered spaces containing discrete pathways such as office buildings. In addition, two different kinds of simulation experiments with Router indicate that the second and the third hypotheses are only partially correct. Finally, we relate the evaluation methods and experimental designs with the research hypotheses.