Open Access. Powered by Scholars. Published by Universities.®

Physical Sciences and Mathematics Commons™

Open Access. Powered by Scholars. Published by Universities.®

Computer Sciences

Brigham Young University

Series

2005

Articles 1 - 19 of 19

Full-Text Articles in Physical Sciences and Mathematics

A Context-Sensitive Structural Heuristic For Guided Search Model Checking, Eric G. Mercer, Neha Rungta Nov 2005

A Context-Sensitive Structural Heuristic For Guided Search Model Checking, Eric G. Mercer, Neha Rungta

Faculty Publications

Software verification using model checking often translates programs into corresponding transition systems that model the program behavior. As software systems continue to grow in complexity and size, exhaustively checking a property on a transition graph becomes difficult. The goal of guided search heuristics in model checking is to find a counterexample to the property being verified as quickly as possible in the transition graph. The FSM distance heuristic builds an interprocedural control flow graph of the program to estimate distance to a possible error state. It ignores calling context and underestimates the true distance to the error.

Go to article

Phylogenetic Analysis Of Large Sequence Data Sets, Hyrum Carroll, Mark J. Clement, Keith Crandall, Quinn O. Snell Oct 2005

Phylogenetic Analysis Of Large Sequence Data Sets, Hyrum Carroll, Mark J. Clement, Keith Crandall, Quinn O. Snell

Faculty Publications

Phylogenetic analysis is an integral part of biological research. As the number of sequenced genomes increases, available data sets are growing in number and size. Several algorithms have been proposed to handle these larger data sets. A family of algorithms known as disc covering methods (DCMs), have been selected by the NSF funded CIPRes project to boost the performance of existing phylogenetic algorithms. Recursive Iterative Disc Covering Method 3 (Rec-I-DCM3), recursively decomposes the guide tree into subtrees, executing a phylogenetic search on the subtree and merging the subtrees, for a set number of iterations. This paper presents a detailed analysis …

Go to article

Linear Equality Constraints And Homomorphous Mappings In Pso, Christopher K. Monson, Kevin Seppi Sep 2005

Linear Equality Constraints And Homomorphous Mappings In Pso, Christopher K. Monson, Kevin Seppi

Faculty Publications

We present a homomorphous mapping that converts problems with linear equality constraints into fully unconstrained and lower-dimensional problems for optimization with PSO. This approach, in contrast with feasibility preservation methods, allows any unconstrained optimization algorithm to be applied to a problem with linear equality constraints, making available tools that are known to be effective and simplifying the process of choosing an optimizer for these kinds of constrained problems. The application of some PSO algorithms to a problem that has undergone the mapping presented here is shown to be more effective and more consistent than other approaches to handling linear equality …

Go to article

Studies In The Dynamics Of Economic Systems, Christophe G. Giraud-Carrier, Kevin Seppi, Nghia Tran, Sean C. Warnick, W. Samuel Weyerman, R. Johnson Aug 2005

Studies In The Dynamics Of Economic Systems, Christophe G. Giraud-Carrier, Kevin Seppi, Nghia Tran, Sean C. Warnick, W. Samuel Weyerman, R. Johnson

Faculty Publications

This paper demonstrates the utility of systems and control theory in the analysis of economic systems. Two applications demonstrate how the analysis of simple dynamic models sheds light on important practical problems. The first problem considers the design of a retail laboratory, where the small gain theorem enables the falsification of pricing policies. The second problem explores industrial organization using the equilibria of profit-maximizing dynamics to quantify the percentage of a firm’s profits due strictly to the cooperative effects among its products. This ”Value of Cooperation” suggests an important measure for both organizational and antitrust applications.

Go to article

Task Similarity Measures For Transfer In Reinforcement Learning Task Libraries, James Carroll, Kevin Seppi Aug 2005

Task Similarity Measures For Transfer In Reinforcement Learning Task Libraries, James Carroll, Kevin Seppi

Faculty Publications

Recent research in task transfer and task clustering has necessitated the need for task similarity measures in reinforcement learning. Determining task similarity is necessary for selective transfer where only information from relevant tasks and portions of a task are transferred. Which task similarity measure to use is not immediately obvious. It can be shown that no single task similarity measure is uniformly superior. The optimal task similarity measure is dependent upon the task transfer method being employed. We define similarity in terms of tasks, and propose several possible task similarity measures, dT, dp, dQ, and dR which are based on …

Go to article

Edge Inference For Image Interpolation, Bryan S. Morse, Neil Toronto, Dan A. Ventura Aug 2005

Edge Inference For Image Interpolation, Bryan S. Morse, Neil Toronto, Dan A. Ventura

Faculty Publications

Image interpolation algorithms try to fit a function to a matrix of samples in a "natural-looking" way. This paper presents edge inference, an algorithm that does this by mixing neural network regression with standard image interpolation techniques. Results on gray level images are presented, and it is demonstrated that edge inference is capable of producing sharp, natural-looking results. A technique for reintroducing noise is given, and it is shown that, with noise added using a bicubic interpolant, edge inference can be regarded as a generalization of bicubic interpolation. Extension into RGB color space and additional applications of the algorithm are …

Go to article

Validating Human–Robot Interaction Schemes In Multitasking Environments, Jacob W. Crandall, Michael A. Goodrich, Curtis W. Nielsen, Dan R. Olsen Jr. Jul 2005

Validating Human–Robot Interaction Schemes In Multitasking Environments, Jacob W. Crandall, Michael A. Goodrich, Curtis W. Nielsen, Dan R. Olsen Jr.

Faculty Publications

The ability of robots to autonomously perform tasks is increasing. More autonomy in robots means that the human managing the robot may have available free time. It is desirable to use this free time productively, and a current trend is to use this available free time to manage multiple robots. We present the notion of neglect tolerance as a means for determining how robot autonomy and interface design determine how free time can be used to support multitasking, in general, and multirobot teams, in particular. We use neglect tolerance to 1) identify the maximum number of robots that can be …

Go to article

Categorizing And Extracting Information From Multilingual Html Documents, Yiu-Kai D. Ng, Seungjin Lim Jul 2005

Categorizing And Extracting Information From Multilingual Html Documents, Yiu-Kai D. Ng, Seungjin Lim

Faculty Publications

The amount of online information written in different natural languages and the number of non-English speaking Internet users have been increasing tremendously during the past decade. In order to provide high-performance access of multilingual information on the Internet, we have developed a data analysis and querying system (DatAQs) that (i) analyzes, identifies, and categorizes languages used in HTML documents, (ii) extracts information from HTML documents of interest written in different languages, (iii) allows the user to submit queries for retrieving extracted information in the same natural language provided by the query engine of DatAQs using a menu-driven user interface, and …

Go to article

Detecting Similar Html Documents Using A Fuzzy Set Information Retrieval Approach, Yiu-Kai D. Ng, Rajiv Yerra Jul 2005

Detecting Similar Html Documents Using A Fuzzy Set Information Retrieval Approach, Yiu-Kai D. Ng, Rajiv Yerra

Faculty Publications

Web documents that are either partially or completely duplicated in content are easily found on the Internet these days. Not only do these documents create redundant information on the Web, which take longer to filter unique information and cause additional storage space, but also they degrade the efficiency of Web information retrieval. In this paper, we present a new approach for detecting similar Web documents, especially HTML documents. Our detection approach determines the odd ratio of any two documents, which makes use of the degrees of resemblance of the documents, and graphically displays the locations of similar (not necessarily the …

Go to article

Comparing High-Order Boolean Features, Adam Drake, Dan A. Ventura Jul 2005

Comparing High-Order Boolean Features, Adam Drake, Dan A. Ventura

Faculty Publications

Many learning algorithms attempt, either explicitly or implicitly, to discover useful high-order features. When considering all possible functions that could be encountered, no particular type of high-order feature should be more useful than any other. However, this paper presents arguments and empirical results that suggest that for the learning problems typically encountered in practice, some high-order features may be more useful than others.

Go to article

Effectively Using Recurrently-Connected Spiking Neural Networks, Eric Goodman, Dan A. Ventura Jul 2005

Effectively Using Recurrently-Connected Spiking Neural Networks, Eric Goodman, Dan A. Ventura

Faculty Publications

Recurrently-connected spiking neural networks are difficult to use and understand because of the complex nonlinear dynamics of the system. Through empirical studies of spiking networks, we deduce several principles which are critical to success. Network parameters such as synaptic time delays and time constants and the connection probabilities can be adjusted to have a significant impact on accuracy. We show how to adjust these parameters to fit the type of problem.

Go to article

Time Invariance And Liquid State Machines, Eric Goodman, Dan A. Ventura Jul 2005

Time Invariance And Liquid State Machines, Eric Goodman, Dan A. Ventura

Faculty Publications

Time invariant recognition of spatiotemporal patterns is a common task of signal processing. Liquid state machines (LSMs) are a paradigm which robustly handle this type of classification. Using an artificial dataset with target pattern lengths ranging from 0.1 to 1.0 seconds, we train an LSM to find the start of the pattern with a mean absolute error of 0.18 seconds. Also, LSMs can be trained to identify spoken digits, 1-9, with an accuracy of 97.6%, even with scaling by factors ranging from 0.5 to 1.5.

Go to article

Correspondence Expansion For Wide Baseline Stereo, Parris K. Egbert, Kevin L. Steele Jun 2005

Correspondence Expansion For Wide Baseline Stereo, Parris K. Egbert, Kevin L. Steele

Faculty Publications

We present a new method for generating large numbers of accurate point correspondences between two wide baseline images. This is important for structure-from-motion algorithms, which rely on many correct matches to reduce error in the derived geometric structure. Given a small initial correspondence set we iteratively expand the set with nearby points exhibiting strong affine correlation, and then we constrain the set to an epipolar geometry using RANSAC. A key point to our algorithm is to allow a high error tolerance in the constraint, allowing the correspondence set to expand into many areas of an image before applying a lower …

Go to article

Active Contours Using A Constraint-Based Implicit Representation, Weiming Liu, Bryan S. Morse, Kalpathi Subramanian, Terry S. Yoo Jun 2005

Active Contours Using A Constraint-Based Implicit Representation, Weiming Liu, Bryan S. Morse, Kalpathi Subramanian, Terry S. Yoo

Faculty Publications

We present a new constraint-based implicit active contour, which shares desirable properties of both parametric and implicit active contours. Like parametric approaches, their representation is compact and can be manipulated interactively. Like other implicit approaches, they can naturally adapt to non-simple topologies. Unlike implicit approaches using level-set methods, representation of the contour does not require a dense mesh. Instead, it is based on specified on-curve and off-curve constraints, which are interpolated using radial basis functions. These constraints are evolved according to specified forces drawn from the relevant literature of both parametric and implicit approaches. This new type of active contour …

Go to article

A Scenario-Based Performance Evaluation Of Multicast Routing Protocols For Ad Hoc Networks, Manoj Pandey, Daniel Zappala Jun 2005

A Scenario-Based Performance Evaluation Of Multicast Routing Protocols For Ad Hoc Networks, Manoj Pandey, Daniel Zappala

Faculty Publications

Current ad hoc multicast routing protocols have been designed to build and maintain a tree or mesh in the face of a mobile environment, with fast reaction to network changes in order to minimize packet loss. However, the performance of these protocols has not been adequately examined under realistic scenarios. Existing performance studies generally use a single, simple mobility model, with low density and often very low traffic rates. In this paper we explore the performance of ad hoc multicast routing protocols under scenarios that include realistic mobility patterns, high density and high traffic load. We use these scenarios to …

Go to article

Prioritized Multiplicative Schwarz Procedures For Solving Linear Systems, Nathaniel Powell, Kevin Seppi, Quinn O. Snell, David Wingate Apr 2005

Prioritized Multiplicative Schwarz Procedures For Solving Linear Systems, Nathaniel Powell, Kevin Seppi, Quinn O. Snell, David Wingate

Faculty Publications

We describe a new algorithm designed to quickly and robustly solve general linear problems of the form Ax = b. We describe both serial and parallel versions of the algorithm, which can be considered a prioritized version of an Alternating Multiplicative Schwarz procedure. We also adopt a general view of alternating Multiplicative Schwarz procedures which motivates their use on arbitrary problems (even which may not have arisen from problems that are naturally decomposable) by demonstrating that, even in a serial context, algorithms should use many, many partitions to accelerate convergence; having such an over-partitioned system also allows easy parallelization of …

Go to article

Fast And Robust Incremental Action Prediction For Interactive Agents, Jonathan Dinerstein, Parris K. Egbert, Dan A. Ventura Feb 2005

Fast And Robust Incremental Action Prediction For Interactive Agents, Jonathan Dinerstein, Parris K. Egbert, Dan A. Ventura

Faculty Publications

The ability for a given agent to adapt on-line to better interact with another agent is a difficult and important problem. This problem becomes even more difficult when the agent to interact with is a human, since humans learn quickly and behave non-deterministically. In this paper we present a novel method whereby an agent can incrementally learn to predict the actions of another agent (even a human), and thereby can learn to better interact with that agent. We take a case-based approach, where the behavior of the other agent is learned in the form of state-action pairs. We generalize these …

Go to article

Prioritization Methods For Accelerating Mdp Solvers, Kevin Seppi, David Wingate Jan 2005

Prioritization Methods For Accelerating Mdp Solvers, Kevin Seppi, David Wingate

Faculty Publications

The performance of value and policy iteration can be dramatically improved by eliminating redundant or useless backups, and by backing up states in the right order. We study several methods designed to accelerate these iterative solvers, including prioritization, partitioning, and variable reordering. We generate a family of algorithms by combining several of the methods discussed, and present extensive empirical evidence demonstrating that performance can improve by several orders of magnitude for many problems, while preserving accuracy and convergence guarantees.

Go to article

Autonomous Vehicle Technologies For Small Fixed-Wing Uavs, Randal Beard, Derek Kingston, Morgan Quigley, Deryl Snyder, Reed Christiansen, Walt Johnson, Timothy Mclain, Michael A. Goodrich Jan 2005

Autonomous Vehicle Technologies For Small Fixed-Wing Uavs, Randal Beard, Derek Kingston, Morgan Quigley, Deryl Snyder, Reed Christiansen, Walt Johnson, Timothy Mclain, Michael A. Goodrich

Faculty Publications

The objective of this paper is to describe the design and implementation of a small semi-autonomous fixed-wing unmanned air vehicle. In particular we describe the hardware and software architectures used in the design. We also describe a low weight, low cost autopilot developed at Brigham Young University and the algorithms associated with the autopilot. Novel PDA and voice interfaces to the UAV are described. In addition, we overview our approach to real-time path planning, trajectory generation, and trajectory tracking. The paper is augmented with movie files that demonstrate the functionality of the UAV and its control software.

Go to article