Showing reports for year: 2005

Title:The USNA Computer Science Department Technical Report Series Information and Guide
Authors:Crabbe, Frederick L.
Serial Number:2005-01
Publication Date:2- 2-2005
Abstract:In January of 2005, the Computer Science Department at the United States Naval Academy launched its own technical report series. The management of submissions and queries is performed automatically with Python scripts. This document describes how the system works and how it should be used to submit technical reports and retrieve reports already submitted.
View ReportView bibtex

Title:The McCallum Projection, Lifting, and Order-Invariance
Authors:Brown, Christopher W.
Serial Number:2005-02
Publication Date:4-22-2005
Abstract:The McCallum Projection for Cylindrical Algebraic Decomposition (CAD) produces a smaller projection factor set than previous projections, however it does not always produce a sign-invariant CAD for the set of input polynomials. Problems may arise when a (k+1)-level projection factor vanishes identically over a k-level cell. According to McCallum's paper, when this happens (and k+1 is not the highest level in the CAD) we do not know whether the projection is valid, i.e. whether or not a sign-invariant CAD for the set of input polynomials will be produced when lifting is performed in the usual way. When the k-level cell in question has dimension 0, McCallum suggests a modification of the lifting method that will ensure the validity of his projection, although to my knowledge this has never been implemented. In this paper we give easily computable criteria that often allow us to conclude that McCallum's projection is valid even though a projection factor vanishes identically over a cell. We also improve on McCallum's modified lifting method. We've incorporated the ideas contained in this paper into QEPCAD, the most complete implementation of CAD. When McCallum's projection is invalid because of a projection factor not being order-invariant over a region on which it vanishes identically, at least a warning message ought to be issued. Currently, QEPCAD may print warning messages that are not needed, and may fail to print warning messages when they are needed. Our implementation in QEPCAD ensures that warning messages are printed when needed, and reduces the number of times warning messages are printed when not needed. Neither McCallum's modified lifting method nor our improvement of it have been implemented in QEPCAD --- the design of the system would make implementing such a feature quite difficult.
View ReportView bibtex

Title:Robot Imitation Learning of High-Level Planning Information
Authors:Crabbe, Frederick L., Hwa, Rebecca
Serial Number:2005-03
Publication Date:5- 2-2005
Abstract:We present a system that enables a robot to learn to plan through demonstration and imitation. An imitator acquires planning operators by observing a demonstrator, segmenting the demonstrators actions into planning steps, and learning the preconditions and effects of the operators. When the imitator tries to execute its own plans, it learns to perform the operations through reinforcement learning, and corrects errors in the previously learned operator effects. Note: This document was originally written in August of 2003, but submitted as a tech report on the above date.
View ReportView bibtex

Title:Low Level Segmentation for Imitation Learning Using the Expectation Maximization Algorithm
Authors:Warner, Andrew D.
Serial Number:2005-04
Publication Date:5- 3-2005
Abstract:Imagine a robot that is able to develop skills on its own, without being programmed directly. This robot would be invaluable in any business, factory, or laboratory. Unfortunately, this problem, known as inductive learning, is very difficult, and has several varieties. One such is imitation learning. The overall process of imitation learning begins with one robot observing another robot performing a task. The watcher then breaks down, or segments, the demonstrating robot s actions into basic actions called planning units. Next the observing robot uses the planning units to create a plan that accomplishes the required task. The execution of a successful plan demonstrates that the robot has correctly implemented an inductive learning process. The scope of this research does not allow the problem of imitation learning to be discussed in its entirety; however, it does investigate an important subset of the larger problem. This paper focuses on the segmentation of the data, specifically how to break it up into the steps that provide the building blocks of the robots ultimate plan.
View ReportView bibtex

Title:An Algorithm for Improving System Safety via Software Fault Trees
Authors:Jones, Sean A., Needham, Donald M. (Advisor)
Serial Number:2005-05
Publication Date:5-26-2005
Abstract:Analysis of software fault trees exposes hardware and software failure events that can lead to unsafe system states, and provides insight on improving safety throughout each phase of a system's development. Although fault trees can be pruned for low severity and low probability nodes, few techniques exist for systematically improving system safety by focusing on cost analysis of a system's fault tree nodes. This paper presents an algorithm for system failure mitigation, supportive of continuous software evolution, based on the reduction of a fault tree into a polynomial expression of degree g, where g is the number of inputs. We combine cost functions that model the expense of improving component reliability into a vector field which provides a measurement of the degree of diffculty of system improvement. The gradient of the vector field is evaluated for vectors providing steep assent towards the area of greatest safety improvement, which in turn provides guidance on improving design time system safety. We provide an example application of our improvement algorithm, and examine improvement verification of the resulting system modifications.
View ReportView bibtex

Title:Establishing Correspondence among Shared Information and Tasks
Authors:Childers, Candace M.
Serial Number:2005-06
Publication Date:6- 7-2005
Abstract:Creating interoperability among heterogeneous systems enhances our military's war-fighting capabilities. Differences in hardware, languages, and data models make interoperability hard to achieve. The Object-Oriented Method for Interoperability (OOMI) resolves modeling differences among systems through construction of a Federation Interoperability Object Model (FIOM) used to capture information and tasks shared among systems. The FIOM is constructed in either a bottom-up or top-down fashion using the OOMI Integrated Development Environment (OOMI IDE) and includes both component system and standard representations of the shared tasks and information. When constructing a federation of interoperable systems, a correspondence must first be established among shared tasks and information before data modeling differences can be resolved. The OOMI IDE uses both semantic and syntactic correlation methodologies for establishing such correspondences. Syntactic correlation is performed using neural networks. Syntactic data concerning the structure and signature of shared information and tasks is used to create discriminator vectors for objects being compared. Neural Networks are used to compare these discriminator vectors to determine the degree of similarity among objects. A ranking of the scores returned from the neural network comparison is used to assist an interoperability engineer in identifying corresponding objects for which modeling differences can be resolved.
View ReportView bibtex

Title:On Quantifer Elimination by Virtual Term Substitution
Authors:Brown, Christopher W.
Serial Number:2005-07
Publication Date:8-24-2005
Abstract:This paper presents a new look at Weispfenning's method of quantifer elimination by virtual term substitution and provides two important improvements. Virtual term substitution eliminates a quantifed variable by substituting formulas in the remaining variables for each atomic formula in which the quantifed variable appears. This paper investigates the polynomials that arise in substitution formulas Weispfenning proposed and, based on this examination, provides a simpler substitution for the general case, and alternate substitutions for several commonly occurring situtions. Providing alternate substitutions allows virtual term substitution to make choices that produce simpler output.
View ReportView bibtex

Title:Midshipmen Blue Force Tracking
Authors:Evans, Paul K., Stahl, David J.
Serial Number:2005-08
Publication Date:12-13-2005
Abstract:This project explores the feasibility of networking Windows CE based handheld devices using inexpensive off-the-shelf hardware and software systems to provide Midshipmen with a tactical training system simulating the FBCB2 system - Force XXI Battle Command, Brigade and Below ("Blue Force Tracking"). In conjunction with the YP Tactical Data Simulator, "Midshipman Blue Force Tracking" is intended to be used as a pedagogical tool for educating midshipmen in the concepts of Network Centric Warfare and operations.
View ReportView bibtex