Recent site activity

Research

Current Research

R. Dolan. "Pheromones Improve Runtime Complexity of Particle Systems".  Submitted to the Journal of Artificial Life.

Abstract: In a typical particle system, the trajectory of each particle depends on forces emanating from all other particles, with closer particles exerting a stronger force. Simulating such a system generally involves calculating pairwise distances, an O(N^{2}) operation at each time step. Cellular systems, on the other hand, involve static networks of cells with local connections, such that the distance between neighboring cells is uniform and constant. Consequently, simulating cellular systems does not require pairwise distance calculations. Instead, updating M cells is a simple O(M) operation. In this paper, we demonstrate an approach to the cellularization of particle systems which eliminates global shared memory. Then, we show that using virtual pheromones improves the runtime complexity of particle systems from O(N^{2}) to O(M). Finally, we use the approach to reduce the runtime complexity of clustering and optimization algorithms.

R. Dolan, D. Caputo. "Cellular-Swarm Optimization, a Scalable Multimodal Swarm Optimizer". Submitted to the Intl. Conf. on Hybrid Intelligent Systems.

Abstract: Particle Swarm Optimization (PSO) and similar optimization algorithms can converge on a suboptimal solution while ignoring other regions of the search space. For some applications, multiple solutions are desired. Here we present a hybrid cellular-swarm optimizer which is capable of optimizing multimodal functions and finding multiple solutions. The biologically-inspired algorithm employs a swarm of particles which emit aggregation pheromones in a cellular medium. Unlike PSO, our algorithm is scalable with respect to the number of modes in the search space and the number of particles dedicated to the search. The approach compares favorably with several PSO-like algorithms when applied to multimodal optimization problems.

R. Dolan. "On the Universality of Cellular-Swarm Computing". Submission pending.

Abstract: Cellular-swarm computing is a hybridization of swarm intelligence algorithms and cellular networks which allows researchers to develop biologically-inspired swarm algorithms while benefiting from the computational simplicity of cellular automata. In the model, swarms of mobile agents interact only via manipulations of a local environment composed of dynamic cells. Information deposited in one cell can propagate through nearby cells to reach other agents through processes such as diffusion or wave propagation. In this way, the environment is used as a medium for interagent communication. By eliminating direct communication among agents, we avoid synchronization issues and improve scalability. This paper discusses the universality of the model when viewed as a discrete automata.

Theses


Abstract: Swarm and cellular computating are powerful paradigms to solve many problems in computer science and engineering. Despite their widespread use, they frequently impose an infeasible complexity in either the formulation or the efficiency of the associated algorithms. In this dissertation, we maintain that a biologically inspired phenomenon, stigmergy, can be used to model massively parallel computations. Our novel model of computation combines swarm agents with a cellular medium through which stigmergic communication is possible. By eliminating direct communication among agents, we demonstrate a powerful, practical, and universal model of computation.

Abstract:  
The inherent massive parallelism of cellular neural networks makes them an ideal computational platform for kernel-based algorithms and image processing. General-purpose GPUs provide similar massive parallelism, but it can be difficult to design algorithms to make optimal use of the hardware. The presented research includes a GPU abstraction based on cellular computation using cellular neural networks. The abstraction offers a simplified view of massively parallel computation which remains universal and reasonably efficient. An image processing library with visualization software has been developed using the abstraction to showcase the flexibility and power of cellular computation on GPUs. A simple virtual machine and language is presented to manipulate images using the library for single-core, multi-core, and GPU back-ends.

Publications

R. Dolan, G. DeSouza, “CNN-based Language and Interpreter for Image Processing on GPUs.” 2010 Int. Journal of Parallel, Emergent, and Distributed Systems.

Abstract: The inherent massive parallelism of cellular neural networks (CNNs) makes them an ideal computational platform for kernel-based algorithms and image processing. General-purpose graphics processing units (GPUs) provide similar massive parallelism, but it can be difficult to design algorithms to make optimal use of the hardware. In this paper, we present a programming environment based on CNNs that can run on GPUs, multi-core CPUs or simply simulated in software. The platform offers a simplified view of massively parallel computation which remains universal and reasonably efficient. An image processing library with visualisation software has been developed using the abstraction to showcase the flexibility and power of cellular computation on GPUs. A simple virtual machine and language is presented to manipulate images using the library for single-core, multi-core and GPU backends.

R. Dolan, G. DeSouza, D. Caputo. "The Swarm Computer, an Analog Cellular-Swarm Hybrid Architecture." 2010 Intl. Conf. on Hybrid Intelligent Systems (HIS 2010).

Abstract: The “killer apps” of cellular and swarm computing are image processing and optimization, respectively; however, applying these platforms to general-purpose computing remains impractical. Designing systems within the restrictive framework of cellular automata is extremely difficult, though often very efficient and scalable. On the other hand, swarm networks are very powerful but difficult to implement in hardware. Here we introduce a hybrid model, the Swarm Computer, which is both practical to program and efficient to implement. Applications in astrophysics and image processing are considered.

R. Meuth, P. Robinette, R. Dolan and D. Wunsch, “Introducing Robots.” Proceedings of the 2009 American Society of Engineering Education Annual Conference and Exposition, Austin, TX, June 14 – 17, 2009.

Abstract: This paper presents the Missouri S&T Introduction to Robotics course which exposes undergraduate and graduate students to technologies behind robotics projects ranging from the historical to the state of the art, as well as fundamentals on robotics architectures, sensing, navigation, and control. Topics covered included basic sensor and image processing, sensor fusion, world modeling, planning, kinematics, control, software agents, machine learning and simulation. Instruction utilized example problems presented by real-world competitions such as the Intelligent Ground Vehicle Competition (IGVC), AHS First Responder, and the Association for Unmanned Vehicle Systems International (AUVSI) Unmanned Aerial Vehicle (UAV) and Unmanned Underwater Vehicle (UUV) competitions.

D. Caputo, R. Dolan, “Fishing for Data: Using Particle Swarm Optimization to Search Data.” Bulletin of the American Astronomical Society, 2010.

Abstract: As the size of data and model sets continue to increase, more efficient ways are needed to sift through the available information. We present a computational method which will efficiently search large parameter spaces to either map the space or find individual data/models of interest.
Particle swarm optimization (PSO) is a subclass of artificial life computer algorithms. The PSO algorithm attempts to leverage "swarm intelligence” against finding optimal solutions to a problem. This system is often based on a biological model of a swarm (e.g. schooling fish). These biological models are broken down into a few simple rules which govern the behavior of the system. "Agents” (e.g. fish) are introduced and the agents, following the rules, search out solutions much like a fish would seek out food. We have made extensive modifications to the standard PSO model which increase its efficiency as-well-as adding the capacity to map a parameter space and find multiple solutions.
Our modified PSO is ideally suited to search and map large sets of data/models which are degenerate or to search through data/models which are too numerous to analyze by hand. One example of this would include radiative transfer models, which are inherently degenerate. Applying the PSO algorithm will allow the degeneracy space to be mapped and thus better determine limits on dust shell parameters. Another example is searching through legacy data from a survey for hints of Polycyclic Aromatic Hydrocarbon emission. What might have once taken years of searching (and many frustrated graduate students) can now be relegated to the task of a computer which will work day and night for only the cost of electricity. We hope this algorithm will allow fellow astronomers to more efficiently search data and models, thereby freeing them to focus on the physics of the Universe.

P. Robinette, R. J. Meuth, R. Dolan, D. Wunsch, “LabRat(TM) : Miniature Robot for Students, Researchers, and Hobbyists,” 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2009).

Abstract:  LabRatTM is an autonomous, self-contained mobile robot kit with batteries, motors, two bumper whisker sensors, and three infrared proximity sensors that double as channels for "Rat-to-Rat" communication. The vehicle determines its position with an optical sensor that detects movement in both lateral directions. The LabRatTM design is completely open source, including software examples and libraries. LabRatTM is designed to fit inside the body of a computer mouse and has applications in the classroom, the lab and the home. The device has been successfully used in an undergraduate robotics class.

R. Dolan, G. DeSouza, “GPU-Based Simulation of Cellular Neural Network for Image Processing,” 2009 International Joint Conference on Neural Networks.

Abstract:  The inherent massive parallelism of cellular neural networks makes them an ideal computational platform for kernel-based algorithms and image processing. General-purpose GPUs provide similar massive parallelism, but it can be difficult to design algorithms to make optimal use of the hardware. The presented research includes a GPU abstraction based on cellular neural networks. The abstraction offers a simplified view of massively parallel computation which remains reasonably efficient. An image processing library with visualization software has been developed to showcase the flexibility and power of cellular computation on GPUs. Benchmarks of the library indicate that commodity GPUs can be used to significantly accelerate CNN research and offer a viable alternative to CPU-based image processing algorithms.

P. Robinette, J. Seiffertt, R. J. Meuth, R. Dolan, D. Wunsch, “An Agent-Based Computational Model of a Self-Organizing Project Management Paradigm for Research Teams,” 2009 International Joint Conference on Neural Networks.

Abstract:  We propose a new research organization management paradigm to increase throughput of projects by allowing researchers to choose their own projects through self-organization. Our methods draw upon the field of Agent-Based computational social science where Artificial Life and simulated societies have been used to study complex systems including economies and financial markets. Modeling the researchers as individual agents, we simulate our new management structure against a more traditional organization where the researchers are broken into departments based on their skills and assigned projects by management. Our results, measuring the amount of time it takes a research organization to serve a given number of contracts, show promise in the less hierarchical approach.

R. J. Meuth, R. Dolan, P. Robinette, J. Jolly, S. Agarwal, D. McAdams, “Modeling Environmental Uncertainty in Ground Robot Navigation,” 18th Annual Argonne Symposium for Undergraduates in Science, Engineering and Mathematics, 2007.

Abstract:  The University of Missouri-Rolla (UMR) Robotics Competition Team has developed an innovative solution to the challenge presented by the Intelligent Ground Vehicle Competition (IGVC). The challenge calls for a ground robot to navigate an obstacle course consisting of boundary lines and upright obstacles. The obstacle course, arranged on a grass field bounded by painted lines, includes construction barrels, heavy-duty netting, cones, trees and simulated potholes.  This competition expects students to focus on advanced path planning, control, and vision algorithms. The base system can be extended with higher-level learning algorithms for any ground vehicle platform. The team's solution is to have the robot develop two models of its environment. The first is simply a map of the obstacles detected by the robot's sensors. The second records the uncertainty of each region in the obstacle model. These models are populated by a vision system and accessed by an intelligent control system to drive the robot.This allows the team's omni-directional robot to look in areas of low certainty while driving in areas of low cost, thus making the robot seem curious and intelligent in its environment.

Conferences

Presentations

R. Dolan, “Cellular-Swarm Computing: Multi-Agent Communication in Dynamic Media with Applications in Massively Parallel Processing.” MU CS Seminar Aug 2011.

R. Dolan, G. DeSouza, D. Caputo, "The Swarm Computer," 2010 Int. Conf. on Hybrid Intelligent Systems.

R. Dolan, D. Caputo, “Sniffing Swarms,” 2009 Mid-American Regional Astrophysics Conference.

R. Dolan, “DAPHNE: A Simulation and Development Environment for Unmanned Systems,” 2007 University of Missouri Science &  Technology Undergraduate Research Conference.

Posters

R. Dolan, G. DeSouza,“Cellular-Swarm Computation,” 2010 University of Missouri Computer Science Poster Competition.

P. Robinette, R. J. Meuth, R. Dolan, D. Wunsch, “LabRat(TM) : Miniature Robot for Students, Researchers, and Hobbyists,” 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2009).

R. Dolan, G. DeSouza, “GPU-Based Simulation of Cellular Neural Networks for Image Processing,” 2009 International Joint Conference on Neural Networks.

R. Dolan, “The Adaptive Bias Perceptron,” 2007 University of Missouri Computational Intelligence Society Poster Competition.