Computer Sciences Commons^™

A Simulated Annealing/Tabu Search Algorithm For The Vehicle Routing Problem, Jeffrey Dale White, Billy E. Gillett

Computer Science Technical Reports

The Vehicle Routing Problem is an NP-complete problem that has been studied extensively since it was introduced in 1958 by G. B. Dantzig and J. H. Ramser. This thesis creates three algorithms that endeavor to find an optimal solution for each problem tested. Two of the algorithms (Simulated Annealing and Tabu Search) have been used previously to solve this problem. These two solution methods are revisited to discover whether a new approach to creating routes will produce the best-known optimal values every time. New routes are created by forming route neighborhoods and then selecting cities from these neighborhoods for insertion. …

Process Driven Software Engineering Environments, John Hayes Lampkin, T. Lo, Daniel C. St. Clair

Computer Science Technical Reports

Software development organizations have begun using Software Engineering Environments (SEEs) with the goal of enhancing the productivity of software developers and improving the quality of software products. The encompassing nature of a SEE means that it is typically very tightly coupled with the way an organization does business. To be most effective, the components of a SEE must be well integrated and the SEE itself must be integrated with the organization.

The challenge of tool integration increases considerably when the components of the environment come from different vendors and support varying degrees of “openness”. The challenge of integration with the …

Subsumption In Modal Logic, Dirk Heydtmann, Ralph W. Wilkerson

Computer Science Technical Reports

Subsumption has long been known as a technique to detect redundant clauses in the search space of automated deduction systems for classical first order logic. In recent years several automated deduction methods for non-classical modal logics have been developed. This thesis explores, how subsumption can be made to work in the context of these modal logic deduction methods.

Many modern modal logic deduction methods follow an indirect approach. They translate the modal sentences into some other target language, and then determine whether there exists a proof in that language, rather than doing deduction in the modal language itself. Consequently, subsumption …

The Difficulty Of Approximating The Chromatic Number For Random Composite Graphs, Jeffrey Wayne Jenness, Billy E. Gillett

Computer Science Technical Reports

Combinatorial Optimization is an important class of techniques for solving Combinatorial Problems. Many practical problems are Combinatorial Problems, such as the Traveling Salesman Problem (TSP) and Composite Graph Coloring Problem (CGCP). Unfortunately, both of these problems are NP-complete and it is not known if efficient algorithms exist to solve these problems. Even approximation with guaranteed results can be just as difficult. Recently, many generalized search techniques have been developed to improve upon the solutions found by the heuristic algorithms.

This paper presents results for CGCP. In particular, exact and heuristic algorithms are presented and analyzed. This study is made, to …

A Syntax-Directed Editor For Borland’S Turbo Pascal, John Gatewood Ham, Thomas J. Sager

Computer Science Technical Reports

This study details the design and implementation of the LSD program, a syntax-directed editor for use in editing the source code for Borland’s Turbo Pascal. LSD is a dual-mode editor which allows both traditional text editing and also grammar-based editing. LSD promotes better programming for novice users by allowing the user to edit the program with a graphical representation of a parse tree. A list of syntactically correct choices is displayed at each point where a choice must be made in the structure of the program. Since only these choices are available, no syntax errors are possible. For more advanced …

Fault-Tolerant Ring Embeddings In Hypercubes -- A Reconfigurable Approach, Jun-Lin Liu, Bruce M. Mcmillin

Computer Science Technical Reports

We investigate the problem of designing reconfigurable embedding schemes for a fixed hypercube (without redundant processors and links). The fundamental idea for these schemes is to embed a basic network on the hypercube without fully utilizing the nodes on the hypercube. The remaining nodes can be used as spares to reconfigure the embeddings in case of faults. The result of this research shows that by carefully embedding the application graphs, the topological properties of the embedding can be preserved under fault conditions, and reconfiguration can be carried out efficiently.

In this dissertation, we choose the ring as the basic network …

Effect Of Joystick Versus Control Yoke Use On Personal Computer (Pc) Flight Training: A Comparative Analysis, Gregory Alan Fontaine

Master's Theses - Daytona Beach

The purpose of this study was to provide a comparative performance analysis of a generic control yoke device and a generic joystick device. The comparison provided data needed for further evaluation of personal computer (PC) aircrew training device (ATD) potential. Both devices were used in support of the same PC flight simulation software program, and were evaluated using the experimental research method. Objective and subjective data were obtained during controlled testing, and subsequently analyzed using basic summation and t-test methods. The results tested the research hypothesis that there is no significant difference in personal computer ATD operator performance using a …

Script-Based Qos Specifications For Multimedia Presentations, Richard Staehli, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Multimedia presentations can convey information not only by the sequence of events but by their timing. The correctness of such presentations thus depends on the timing of events as well as their sequence and content. This paper introduces a formal specification language for playback of real-time presentations. The main contribution of this language is a quality of service (QOS) specification that relaxes resolution and synchronization requirements for playback. Our definitions give a precise meaning to the correctness of a presentation. This specification language will form the basis for a QOS interface for reservation of operating system resources.

Design And Development Of A Heterogeneous Parallel Computing System, Eruch R. Rustomji

Masters Theses

A parallel and distributed processing environment can be defined as one where a set of workstations is configured in a certain topology (such as completely connected linear chain) to simulate the working of a particular parallel architecture. Such an environment provides an extremely useful means of experimenting with parallel algorithms, without the use of expensive dedicated parallel machines.

Several parallel and distributed processing environments exist, such as Parallel Virtual Machine, The Condor System and the Reactive Kernel System/ Cosmic Environment System. Each of these systems has some unique features and limitations. Other systems include p4, Hermes, Linda and Express.

This …

Graphical Event-Directed Scenario Behavioral Specifications For The Scenario-Based Engineering Process (Sep) Using A Domain Specific Software Architecture (Assa) Philosophy, Miao Xia

Computer Science and Engineering Theses - Archive

This thesis extends scenarios of a system into real-time event digraphs. A scenario is an event trace resulting from a particular thread of system execution. An event digraph is an event network. Multiple external stimuli result in a wave of execution in distributed and parallel architecture. A graph theoretic formal definition for event digraphs is developed with the finite sets of events and the scenario event order (SEO). A scenario language is developed from the event digraph. In modeling an event digraph, we introduce the frontier expansion mechanism which let the users and the developers go around the question if …

Design And Construction Of The Aerobot Robotic Manipulator (Arm), William L. Cochran

Theses and Dissertations

This thesis designed, constructed, and tested a robotic arm for the Aerobot Aerial Robot. The main purpose of the ARM is to enable the Aerobot to retrieve objects for use in an annual robotics competition. Design of the ARM involved synthesizing the characteristics of simplicity, weight, strength, and size. The result was a three-degree-of-freedom manipulator that uses electric motors, cable linkages, and telescoping tubes to access a work space below the Aerobot. Forward and inverse kinematics were investigated to enable automation of the ARM. Data was collected from infrared sensors to validate the model. Manipulation of the ARM is presently …

A Numerical Study Of High-Speed Missile Configurations Using A Block- Structured Parallel Algorithm, Douglas C. Blake

Theses and Dissertations

A numerical analysis of the aerodynamic phenomena associated with the high-speed flight of a sharp-nosed, four-finned, high-fineness ratio missile using a block-structured, parallel computer algorithm is presented. The algorithm, PANS-3EM, utilizes a second-order-accurate, shock-capturing, Total Variation Diminishing scheme and incorporates a Baldwin-Lomax turbulence model. PANS-3EM allows for extreme flexibility in the choice of computational domain decomposition and computing machine of implementation. Developmental work consists of conceptualization and verification of the algorithm as well as parallel performance and scalability studies conducted on a variety of computing platforms. Using PANS-3EM, the aerodynamic characteristics of the missile are investigated. Drag and pitching moment …

Genetic Algorithms And Their Application To The Protein Folding Problem, Donald J. Brinkman

Theses and Dissertations

The protein folding problem involves the prediction of the secondary and tertiary structure of a molecule given the primary structure. The primary structure defines sequence of amino-acid residues, while the secondary structure describes the local 3-dimensional arrangement of amino-acid residues within the molecule. The relative orientation of the secondary structural motifs, namely the tertiary structure, defines the shape of the entire biomolecule. The exact, mechanism by which a sequence of amino acids protein folds into its 3- dimensional conformation is unknown Current approaches to the protein folding problem include calculus-based methods, systematic search, model building and symbolic methods, random methods …

A Parallel Computational Fluid Dynamics Unstructured Grid Generator, Deborah E. Davis

Theses and Dissertations

This research addressed the development of a parallel computational fluid dynamics unstructured grid generator using Delaunay triangulation. The generator is applied to simple elliptical and cylindrical two-dimensional bodies. The methodologies used included Watsons point insertion algorithm, Holmes and Snyders point creation algorithm, a discretized surface definition, Andersons clustering function, and a Laplacian smoother. The first version of the software involved a processor boundary exchange at the end of each iteration with no inter-processor communications during the iterations The second version used inter-processor communication during each iteration instead of the boundary exchange. Version 1 demonstrated a speedup of 1.8 for some …

Developing A Sophisticated User Interface To Support Domain-Oriented Application Composition And Generation Systems, Jay A. Cossentine

Theses and Dissertations

This research refined the visual presentation and usability of a previously developed visual interface for a domain-oriented application composition and generation system. The refined visual interface incorporated domain-specific bit-mapped graphics and sophisticated user interface design concepts to reduce user workload. User workload was reduced through object layout, window design, and color utilization techniques; by combining repetitive procedures into single commands; and reusing, rather than recreating, composition information throughout the application composition process. The Software Refinery environment, including its graphical interface tool INTERVISTA, was used to develop techniques for visualizing and manipulating objects contained in a formal object base. INTERVISTA was …

Alternative Architectures For Domain-Oriented Application Composition And Generation Systems, Warren E. Gool

Theses and Dissertations

This thesis presents a formalized framework for comparing the structure and semantics of software architectures. The framework uses object diagrams for analyzing the structure of the architectures and the axiomatic approach for analyzing the semantics. This framework is used to compare the Object Connection Update OCU model developed by the Software Engineering Institute against four other software architectures VHDL defined by Lipsett, MetaH defined by Honeywell, microRapide defined by Luckham, and hierarchical software systems as defined by Batory. The goal of the comparison was to evaluate the OCU model for suitability within prototype application composition and generation systems. This research …

Using Database Technology To Support Domain-Oriented Application Composition Systems, Danny A. Cecil, Joseph A. Fullenkamp

Theses and Dissertations

This research designed and prototyped an OODBMS technology base to store and retrieve various types of domain artifacts for domain-oriented application composition systems (DOACS). We developed object-oriented database schemas for a validating domain and the Object-Connection-Update software architecture. We implemented an inheritance relationship between the schemas so a domain model can inherit an architectural structure from an architecture model allowing us to isolate domain-specific knowledge from architecture-specific knowledge. We also developed a meta-model to formally define domain models in the database. We then developed a set of database methods to transform a domain model into a database schema for storing …

A Distributed Interactive Simulation Based Remote Debriefing Tool For Red Flag Missions, Michael T. Gardner

Theses and Dissertations

Air Force leaders, recognizing the need for improved training following the Vietnam War, implemented the Red Flag exercises at Nellis AFB. At the heart of this training is the Red Flag Measurement and Debriefing System RFMDS and its capability to accurately reconstruct the elements of an intense exercise fought over the deserts of Nevada. This thesis uses the technology of distributed interactive simulation DIS to transmit aircraft telemetry onto computer networks, allowing the monitoring and analysis of live Red Flag missions at any site with compatible communications equipment and thesis software. The use of standard DIS protocols enables simulators to …

Integration And Enhancement Of The Saber Wargame, Karl S. Mathias

Theses and Dissertations

The Saber wargame is a theater-level air/land battle wargame written in Ada that is being developed for the Air Force Wargaming Center at Maxwell AFB, AL. This thesis documents how the user interface and simulation engine were integrated. Integration was accomplished by developing a portable object-oriented database system (OODBMS) interface. The interface was implemented in Ada and tied to an OODBMS also written in Ada. Using the interface, both subsystems were able to work from a consistent database and exchange information. The user interface was enhanced by converting it from the Software Technology for Adaptable Reliable Systems Ada/X Window System …

A Prototype Architecture For An Automated Scenario Generation System For Combat Simulations, Mark W. Pfefferman

Theses and Dissertations

This research effort examines the problem of automating the scenario generation process and presents a prototype architecture for an automated scenario generation system. This architecture is designed using an object- oriented approach which leads to a modular and modifiable design. The architecture provides a mechanism for automatically generating scenario files from a textual US Army operation order. This translation process occurs in two phases. First, the text operation order is translated into an intermediate format called the mission file. In the second phase, the system reads the mission file, instantiates intelligent entities, and assigns missions to those entities. The intelligent …

Design Of A Shared Coherent Cache For A Multiple Channel Architecture, John A. Reisner

Theses and Dissertations

The Multiple Channel Architecture MCA is a recently proposed computer architecture which uses fiber optic communications to overcome many of the problems associated with interconnection networks. There exists a detailed MCA simulator which faithfully simulates an MCA system, however, the original version of the simulator did not cache shared data. In order to improve the performance of the MCA, a cache coherency protocol was developed and implemented in the simulator. The protocol has two features which are significant: (1) a time-division multiplexed TDM communication bus is used for coherency traffic, and (2) the shared data is cached in an independent …

Objectsim - A Reusable Object Oriented Dis Visual Simulation, Mark I. Snyder

Theses and Dissertations

This research designed and implemented a reusable Distributed Interactive Simulation DIS visual simulation architecture for Silicon Graphics platforms. The goal was to research software architecture technologies and to create a design and implementation using these ideas. The architecture was designed using object oriented techniques to provide the ability to customize it via inheritance extension. The resulting design was implemented using C and applied to several DIS visual simulation projects in the Graphics Lab at AFIT. The architecture, named ObjectSim, was successful in its goal of providing a reusable core for the DIS visual simulation projects in the Graphics Lab at …

Object Interaction In A Parallel Object-Oriented Discrete-Event Simulation, Walter G. Trachsel

Theses and Dissertations

This thesis investigates object interaction issues involved in developing an object-oriented parallel discrete-event simulation and develops a simulation model that provides object interaction capabilities. The research covers issues in object representation, object interaction, object management. discrete-event simulation, and parallel simulation. There are three primary types of objects that the research discusses. The first type is a basic simulation object, whose size and behavior is insignificant compared to the size of the simulation as a whole. The second type is an aggregate object which consists of smaller component objects that interact and affect the performance of the larger object as a …

A Method For Populating The Knowledge Base Of Afit's Domain-Oriented Application Composition System, Russell M. Warner

Theses and Dissertations

This research developed a formal method for adding new domains to Architect, a domain-oriented application composition system being developed at the Air Force Institute of Technology AFIT to explore new software engineering technologies. Using canonical formal specifications of domain objects, Architect rapidly composes these specifications into a software application and executes a prototype of that application as a means to demonstrate its correctness before any programming language specific code is generated. Architect is implemented in the Software Refinery environment, which allows Architect to create and manipulate object-oriented specifications. As a part of this research effort, domain-oriented application composition systems were …

Three Dimensional Object Recognition Using A Complex Autoregressive Model, David E. Chelen

Theses and Dissertations

Based on an autoregressive model, Complex Partial Correlation CPARCOR features are known to provide exceptional Position, Scale, and Rotation Invariant PSRI properties for planar 2-Dimensional 2-D object recognition. Although autogressive models have been successfully applied to numerous spatio-temporal recognition tasks, the effects of out-of-plane image rotations were never considered. This study investigates application of the CPAR-COR model to a five class problem of nonplanar 2-D views of 3-D objects. Recognition based on CPAR-COR features is evaluated using a Template Matching algorithm, two K-Nearest-Neighbor KNN classifiers, and a Hidden Markov Model HMM. Direct comparisons to recognition based on Fourier features are …

Discovery Learning In Autonomous Agents Using Genetic Algorithms, Edward O. Gordon

Theses and Dissertations

As the new Distributed Interactive Simulation (DIS) draft standard evolves into a useful document and distributed simulations begin to emerge that implement parts of the standard, there is renewed interest in available methods to effectively control autonomous aircraft agents in such a simulated environment. This investigation examines the use of a genetics-based classifier system for agent control. These are robust learning systems that use the adaptive search mechanisms of genetic algorithms to guide the learning system in forming new concepts (decision rules) about its environment. By allowing the rule base to evolve, it adapts agent behavior to environmental changes. Addressed …

Graphical Tools For Situational Awareness Assistance For Large Battle Spaces, Brian B. Soltz

Theses and Dissertations

As virtual environments grow in complexity and size, users are increasingly challenged in assessing situations in large-scale virtual environment. This occurs because of the difficulty in determining where to focus attention and assimilating and assessing the information as it floods in. One technique for providing this type of assistance is to provide the user with a first-person, immersive, synthetic environment observation post, that permits unobtrusive observation of the environment without interfering with the activity in the environment. However, for large, complex synthetic environments, this type of support is not sufficient because the portrayal of raw, unanalyzed data in the virtual …

Processing Of Wide-Angle Synthetic Aperture Radar Signals For Target Detection, Kurt W. Knurr

Theses and Dissertations

This study investigated methods of targets detection using Wide-Angle Synthetic Aperture Radar (WASAR). WASAR uses multiple aspect angle Synthetic Aperture Radar (SAR) images of the same scene. The SAR images were generated using a pre-release software package from package from Loral Corporation. The software was able to generate 512 by 512 pixel SAR images that contained various vegetation return which for our purposes we classified as clutter. Within this clutter, targets (M35 trucks) could be placed at random location and orientations. The software also had the capability of generating fully- polarimetic WASAR images with multiple depression angles. This data was …

Identity Verification Through The Fusion Of Face And Speaker Recognition, John G. Keller

Theses and Dissertations

In this research, face recognition and speaker identification systems are each converted into verification systems. The two verification systems are then fused to form a single identity verification system. Finally, the use of the Karhunen-Loeve Transform (KLT) for dimensional reduction is examined for suitability in the verification task. The base face recognition system used the KLT for feature reduction and a back-propagation neural net for classification. Verification involved training a net for each individual in the database for two classes of outputs, 'Joe' or 'not Joe.' The base speaker identification system used Cepstral analysis for feature extraction and a distortion …

Synthetic Battlebridge: Information Visualization And User Interface Design Applications In A Large Virtual Reality Environment, Kirk G. Wilson

Theses and Dissertations

With shrinking budgets and fewer personnel, future military training will rely heavily on simulated environments. The goal for this training is to reduce cost while maintaining readiness and unparalleled capability for all levels of military command. This thesis effort, the Synthetic Battle Bridge SBB , provides a real-time simulated environment for military commanders to observe on-going computer simulations of varying participation levels and helps them wring the most from a simulation. The SBB, designed for higher ranking personnel with little time to spend learning how to run the system, must exhibit three capabilities ease-of-use, long-term retention, and adaptability. Based on …