June 22, 2003
June 22, 2003
June 25, 2003
8.995.1 - 8.995.8
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
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
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
Dannelly, R. S., & Steidley, C. (2003, June), Robots And Search Algorithms: Real World Applications For Students Paper presented at 2003 Annual Conference, Nashville, Tennessee. https://peer.asee.org/11433
ASEE holds the copyright on this document. It may be read by the public free of charge. Authors may archive their work on personal websites or in institutional repositories with the following citation: © 2003 American Society for Engineering Education. Other scholars may excerpt or quote from these materials with the same citation. When excerpting or quoting from Conference Proceedings, authors should, in addition to noting the ASEE copyright, list all the original authors and their institutions and name the host city of the conference. - Last updated April 1, 2015