Browsing by Author "Miller, David P."
Now showing 1 - 13 of 13
Results Per Page
Sort Options
- Designing a testing strategy for expert systemsHite, Lee Anne (Virginia Tech, 1988-02-15)Testing programs with tractable algorithms is one area in which software engineers have made numerous advances over the past few decades. Testing rule-based expert systems, however, is a new area in software engineering which requires new testing techniques. For the most part, traditional software engineering testing strategies assume modular program development. This assumption is impractical to make for expert system development, for the knowledge base of an expert system is quite simply a huge non-modular program. It consists almost entirely of non-ordered, multi-branching decision statements. In traditional programming, the module interfaces are limited and well defined. For rule-based expert systems, the interaction among rules is combinatoric and highly data-driven. Thus, the testing of a completed expert system via traditional path analysis is impractical. The design of a testing strategy for expert systems focuses on the generic phases of expert system development. Briefly, these phases include system definition, incremental system implementation, and system maintenance.. Using this simplified breakdown of the expert system development process as a guide, certain testing techniques can be generalized enough to work for any expert system application.
- Designing a Testing Strategy for Expert SystemsHite, Lee Anne; Miller, David P. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1988)Testing programs with tractable algorithms is one area in which software engineers have made numerous advances over the past few decades. Testing rule-based expert systems, however, is a new area in software engineering which requires new testing techniques. For the most part, traditional software engineering testing strategies assume modular program development. This is assumption impractical to make for expert system development, for the knowledge base of an expert system is quite simply a huge non-modular program. It consists almost entirely of non-ordered, multi-branching decision statements. In traditional programming, the module interfaces are limited and well defined. For rule-based expert systems, the interaction among rules is combinatoric and highly data-driven. Thus, the testing of a completed expert system via traditional path analysis is impractical. The design of a testing strategy for expert systems focuses on the generic phases of expert system development. Briefly, these phases include system definition, incremental system implementation, and system maintenance. Using this simplified breakdown of the expert system development process as a guide, certain testing techniques can be generalized enough to work for any expert system application.
- Error patterns: what do they tell us?Orey, Michael Andrew (Virginia Tech, 1987-10-15)An analysis of computer diagnostic systems shows that most systems use answer data (product) for their analyses. This process of determining an error pattern, in addition, does little in the way of telling a teacher what should be done to help the child. This two-fold problem, extant in all computerized arithmetic diagnostic systems to date, prompted this study which sought other data sources in order to bring about more accurate computer analyses. A cognitive orientation suggested that the use of clinical diagnostic techniques should be explored as an alternative to error analysis. Essentially, these two approaches were compared. That is, to what extent does error pattern diagnosis (an essentially product oriented approach) and clinical mathematical diagnosis (a process oriented approach) interrelate? Participants for this study were five, eight year olds from southwest Virginia. These children completed a test that was developed by Van Lehn (1982). This test was analyzed for error patterns and the children were selected on the basis of their error patterns. These children were then tested in a clinical setting using a measure developed for this study in cooperation with a clinical mathematics diagnostician. The analysis was done on the results of these two measures and the protocols collected during the clinical interviews. The results indicated that there was no clear connection between the two types of diagnosis, but the analysis did yield a broader description of each individual participant. That is, error analysis or clinical mathematics alone does not completely describe an individual's knowledge of mathematics.
- Fault diagnosis based on causal reasoningWhitehead, John Douglass Hodjat (Virginia Tech, 1987-11-13)A "causal" expert system based on hypothetical reasoning and its application to a Mark 45 turret gun's lower hoist are described. HOIST is a system that performs fault diagnosis without the use of a domain expert or "shallow rules". Rather its "knowledge" is coded directly from a structural specification of the Mark 45 lower hoist. The technology reported here for assisting the lesser acquainted diagnostician differs considerably from the normal rule-based expert system techniques: it reasons about machine failures from a functional model of the device. In a mechanism like the lower hoist, a functional model must reason about forces, fluid pressures and mechanical linkages, that is, qualitative physics. HOIST technology can be directly applied to any exactly specified device for modeling and diagnosis of single or multiple faults. Hypothetical reasoning, the process embodied in HOIST, has general utility in qualitative physics and reason maintenance.
- Low Error Path Planning for a Synchro-Drive Mobile RobotMiller, David P.; Koushik, Prabhakar M. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1986)A path-planning system is presented which, given any points, calculates a low-error path for a synchro-drive robot. The path reduces dead-reckoning errors by using gentle, constant curvature turns for switching directions of the robot's travel---yet direct and minimal length travel are maintained. The system has been implemented and tested with a Vectrobot mobile platform.
- Musical expression in automated composition of melodiesMcLintock, Brian Thomas (Virginia Tech, 1987-11-20)Music composed by computers has always been lacking in "musical" qualities: mood, emotional expression and a sense of purposefulness or goal. A musical expert system, called EMOTER, is the first attempt to address these important musical aspects. EMOTER receives as input a list of moods (e.g., happy, lively) and generates melodic passages intended to evoke those moods in an organized, coherent fashion. EMOTER composes the basic units of music called phrases. The program uses the mood-specification from a theory due to Deryck Cooke to derive a few motifs (very primitive melodic material) exemplifying the moods and computes a number of musical attributes to guide its compositional choices. A theory of emotion due to Leonard Meyer further helps plan the phrase. The theory states that an emotional response is stimulated in a listener when expectations about the progression of the music are first established and then inhibited (with the understanding that the expectations will eventually be fulfilled). A melodic passage is composed using the selected motifs, attributes and emotional theory to create a "skeletal" phrase. This is embellished and developed (also using the attributes and theory) to flesh-out the bare melodic material into a passage that embodies the musical characteristics of the mood-specification. Results with EMOTER are excellent. Many musical phrases comparable to music of normal composers are generated from a single mood-specification. More theory is needed, however, before the full complexities of human-composed music are sufficiently captured in code for EMOTER to pass a Turing test in music composition.
- Path Planning Through Time and Space in Dynamic DomainsSlack, Marc G.; Miller, David P. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1987-05-01)Realistic robot problems involve navigating the robot through time as well as space. The obstacles that a robot must avoid and the pathways on which it travels are subject to changes throughout time. These changes can occur in a predictable or unpredictable fashion. This paper presents an integrated route planning and spatial representation system that allows paths to be calculated in dynamic domains. The path planner finds the "best route" through a given n-dimensional space. The "best route" is defined as the path through space-time with the best score as determined by a set of user-defined evaluation
- Reasoning About Knowledge Using Extensional LogicsGat, Erann; Miller, David P. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1987)When representing statements about knowledge in a extensional logic, it occasionally happens that undesired conclusions arise. Such extraneous conclusions are often the result of substitution of equals for equals or existential instantiation within intensional operators such as Know. In the past, efforts at solving this problem have centered on modifications to the logic. In this thesis, I propose a solution that leaves the logic intact and changes the representation of the statements instead. The solution presented here has four main points: 1) Only propositions can be known. 2) Relations rather than functions should be used to describe objects. 3) Temporal reasoning is often necessary to represent many real-world problems. 4) In cases where more than one label can apply to the same object, an agent's knowledge about labels must be explicitly represented. When these guidelines are followed, statements about knowledge can be represented in standard first-order predicate logic in such a way that extraneous conclusions cannot be drawn. Standard first-order theorem provers (like Prolog) can then be used to solve problems which involve reasoning about knowledge.
- Reliable goal-directed reactive control of autonomous mobile robotsGat, Erann (Virginia Tech, 1991-04-19)This dissertation demonstrates that effective control of autonomous mobile robots in real-world environments can be achieved by combining reactive and deliberative components into an integrated architecture. The reactive component allows the robot to respond to contingencies in real time. Deliberation allows the robot to make effective predictions about the world. By using different computational mechanisms for the reactive and deliberative components, much existing deliberative technology can be effectively incorporated into a mobile robot control system. The dissertation describes the design and implementation of a reactive control system for an autonomous mobile robot which is explicitly designed to interface to a deliberative component A programming language called ALF A is developed to program this system. The design of a control architecture which incorporates this reactive system is also described. The architecture is heterogeneous and asynchronous, that is, it consists of components which are structured differently from one another, and which operate in parallel. This prevents slow deliberative computations from adversely affecting the response time of the overall system. The architecture produces behavior which is reliable and goal-directed, yet reactive to contingencies, in the face of noise, limited computational resources, and an unpredictable environment. The system described in this dissertation has been used to control three real robots and a simulated robot performing a variety of tasks in real-world and simulated real-world environments. A general design methodology based upon bottom-up hierarchical decomposition is demonstrated. The methodology is based on the principle of cognizant failure, that is, that low-level activities should be designed in a way as to detect failures and state transitions at high levels of abstraction. Furthermore, the results of deliberative computations should be used to guide the robot's actions, but not to control those actions directly.
- A Sensory Input System for Autonomous Mobile RobotsBixler, J. Patrick; Miller, David P. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1987)In order to accomplish navigation in an similar world a robot must be able to build and update its own world map continuously and in real time. This paper proposes a sensory input system based on the fusion of simple low-resolution vision with directed high-resolution sonar. The basic idea is to use a simple vision system to locate the position in which an obstacle lies, and then use an ultrasonic rangefinder to determine the depth of the object and to gain clues about its shape. By fusing two simple systems we attempt to exploit the strengths of each while maintaining an acceptable computational cost. An idealized example is given and we discuss the possibilities and some of the problems.
- Situationally driven local navigation for mobile robotsSlack, Marc G. (Virginia Tech, 1990)For mobile robots to autonomously accommodate dynamically changing navigation tasks in a goal-directed fashion, they must employ navigation plans. Any such plan must provide for the robot’s immediate and continuous need for guidance while remaining highly flexible in order to avoid costly computation each time the robot’s perception of the world changes. Due to the world’s uncertainties, creation and maintenance of navigation plans cannot involve arbitrarily complex processes, as the robot’s perception of the world will be in constant flux, requiring modifications to be made quickly if they are to be of any use. This work introduces Navigation Templates (or NaTs) which are building blocks for the construction and maintenance of rough navigation plans which capture the relationship that objects in the world have to the current navigation task. By encoding only the critical relationship between the objects in the world and the navigation task, a NaT-based navigation plan is highly flexible; allowing new constraints to be quickly incorporated into the plan and existing constraints to be updated or deleted from the plan. To satisfy the robot’s need for immediate local guidance, the NaTs forming the current navigation plan are passed to a transformation function. The transformation function analyzes the plan with respect to the robot’s current location to quickly determine (a few times a second) the locally preferred direction of travel. This dissertation presents NaTs and the transformation function as well as the needed support systems to demonstrate the usefulness of the technique for controlling the actions of a mobile robot operating in an uncertain world. ¹ This work was supported in part by a grant from the Jet Propulsion Laboratory under a contract from the National Aeronautics and Space Administration, and by a grant from the Naval Surface Weapons Center.
- Spatial and Temporal Path PlanningSlack, Marc G.; Miller, David P. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1987)For robots to move out of the lab and into the real-world, they must be able to plan routes not only through space but through time as well. The introduction of a time factor to the planning process implies that robots must reason about other processes and agents that move through space independently of the robot's actions. This thesis presents an integrated route planner and spatial representation system for planning real-time paths through dynamic domains called Robonav. Robonav will find the safest, most efficient route through time and space as described by an evaluation function. Due to the design of the spatial representation and the mechanics of the algorithm, Robonav has an isomorphic mapping onto a machine with a highly parallel SIMD architecture. When Robonav is operated in a predictable domain; paths are found in O(p) time (where p is the length of a path). In unpredictable domains, where Robonav is operated in incremental mode, paths are found and executed in $O(p^2)$ time.
- A Task and Resource Scheduling System for Automated PlanningMiller, David P. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1987)Planning is done at both the strategic and tactical levels. This paper classifies some previous planning techniques into these different levels, and details some of their problems. A planning technique known as heuristic task scheduling is then presented along with a planner architecture that integrates task-scheduling with more traditional techniques to form a system that bridges the strategic/tactical deviation.