Search in the Physical World
Creators: name: Hollinger, Geoffrey A.
Publisher: name: Carnegie Mellon University
Year: 2010
Subjects: subject: 80101 Adaptive Agents and Intelligent Robotics
subject: FOS: Computer and information sciences
subject: FOS: Computer and information sciences

description: This thesis examines search in the physical world, which differs significantly from<br> the searches in the digital world that we perform every day on our computers. When<br> searching the internet, for instance, success is a matter of informed indexing that<br> allows the information to be retrieved quickly. In these cases, there is no consideration<br> of the physical nature of the world, and the search is not cognizant of space,<br> time, or traversal distance. In contrast, search in the physical world must consider a<br> target that could be continuously moving, possibly even trying to evade being found.<br> The environment may be partially known, and the search proceeds with information<br> gathered during the search itself. In many cases, such as guaranteeing capture of<br> an adversarial target, the problem cannot be solved with a single searcher, and all<br> group members must coordinate their actions with others on the team. Prior work<br> has explored limited instances of such problems, but existing techniques either scale<br> poorly or do not have performance guarantees.<br> Two of the main variations of search in the physical world are considered: efficient<br> search and guaranteed search. During efficient search, robots move to optimize the<br> average-case performance of the search given a model of the target’s motion. During<br> guaranteed search, robots coordinate to minimize the worst-case search time if<br> the target is adversarial. This thesis unifies these search problems and shows them<br> to be NP-hard, which suggests that a scalable and optimal algorithm is unlikely.<br> In addition, it is shown that efficient search admits a bounded approximation, and<br> guaranteed search does not. Despite these hardness results, algorithms using implicit<br> coordination can provide scalable and high-performing solutions to many real-world<br> search problems. Implicit coordination is defined as the sharing of locations, measurements,<br> and/or actions to improve the team plan. In accord with this design strategy,<br> a linearly scalable efficient search algorithm is presented that utilizes implicit coordination<br> to achieve bounded performance. In addition, this thesis contributes a novel<br> approach that augments the coordination with a pre-search spanning tree generation<br> step, which leads to an anytime algorithm for guaranteed search.<br> With a focus on decentralized and online operation, the proposed search algorithms<br> are extended to take into account team constraints, limited communication,<br> and partially known environments. The techniques are illustrated using a scenario<br> from the literature that incorporates both efficient and guaranteed search, and they<br> are validated both in simulation and on human-robot search teams operating in the<br> physical world. The developed framework enables teams of autonomous agents to<br> search environments outside the scope of previous techniques, and the analysis provides<br> insight into the complexity of multi-robot coordination problems