Paper Authors

Abstract

NOTE: The first page of text has been automatically extracted and included below in lieu of an abstract

Session 1320

Robots and Search Algorithms: Real-World Applications for Students R. Stephen Dannelly, Carl W. Steidley, Mario A. Garcia, and Sreevani Pelala

Texas A&M University Corpus Christi

Abstract

Frequently in the Computer Science curriculum we introduce topics in an abstract fashion in which the abstraction seems perfectly straightforward as well as easily implementable to students. Such is the topic of search. Generally, the topic of search is introduced to students as early as the data structures course where the student is introduced to various algorithms for the search of tree structures. In this light, students understand and are able to implement search as an abstract method of information retrieval. However, in this paper we describe a project in which students implement one kind of goal-based agent called a problem-solving agent. The development and implementation of this agent required the construction of a search process to find solutions to real-world physical problems.4,8

Introduction

A main element in analyzing a problem is the state space in which the problem exists, which describes all the possible configurations of the environment. In robotics, the environment includes the body of the robot itself. Both the configuration of the robot’s body and the locations of objects in physical space are defined by real-valued coordinates. It is therefore impossible to apply standard search algorithms in any straightforward way because the numbers of states and actions are infinite. Much of the work in robot planning has dealt with ways to tame these continuous state spaces.

The question of moving a robot around successfully can be considered as problems of motion in a configuration space. Algorithms that handle a configuration space directly assume that an exact description of the space is available, so they cannot be used where there is significant sensor error and motion error. In some cases, no description of the space is available until the robot starts moving around in it. Russell and Norvig 5 identify five major classes of navigation and motion planning algorithms. We arrange them below roughly in the order of the amount of information required at planning and execution times:

Cell decomposition-these methods break continuous space into a finite number of cells, yielding a discrete search problem.

Skeletonization- these methods compute a one-dimensional “skeleton” of the configuration space, yielding an equivalent graph search problem.

Proceedings of the 2003 American Society for Engineering Education Annual Conference & Exposition Copyright © 2003, American Society for Engineering Education

• Citation

• Format
  • APA
  • APA - LaTeX bibitem
  • MLA
  • MLA - LaTeX bibitem
  • Bibtex
  • EndNote - RIS

Dannelly, R. S., & Steidley, C. (2003, June), Robots And Search Algorithms: Real World Applications For Students Paper presented at 2003 Annual Conference, Nashville, Tennessee. 10.18260/1-2--11433