Comparing AI Search Algorithms and Their Efficiency When Applied to Path Finding Problems
Year of Dissertation:
2012
Various Artificial Intelligence (AI) search algorithms have been investigated and classified as unidirectional or bidirectional. We start our discussion by presenting certain unidirectional and bidirectional search algorithms (BDS). We continued our study by presenting contributions to the field of search algorithms in AI. The focus of this research is the study of the bidirectional search and certain classes of AI problems and some new approaches to the domain of AI search algorithms have been explored. The second contribution of this research is to compare problem representations and to exploit built-in features of diverse programming paradigms. The programing paradigms have been classified by the problem domains which they might be more suitable for. This has been justified by the fact that the evaluation of search algorithms is a well-studied area of Artificial Intelligence (AI). However evaluation of the performance of programming paradigms when applied to search algorithms has not been studied well. We conclude our discussion with experimental results and more detailed information about our implementations.
Game-theoretic and Bio-inspired Techniques for Self-positioning Autonomous Mobile Nodes
Year of Dissertation:
2012
Autonomous mobile nodes that position themselves over an unknown terrain can ameliorate many of the problems which mobile ad hoc networks (MANETs) face. Achieving good spatial placement of mobile agents leads to superior network topology with improved area coverage, reduced power consumption, enhanced spectrum utilization, and simplified routing procedures. However, autonomous decision-making by nodes may also increase uncooperative and selfish behavior by these independent agents. Since it is impractical in MANETs to sustain complete and accurate information at each node about the entire network layout and decision of an individual node about its position should only be based on local information with limited coordination among agents. These characteristics recommend game theory (GT) as a tool for modeling, analyzing, and designing many MANET applications. At the same time, biologically inspired computation techniques such as genetic algorithms (GAs) can be used for finding desirable solutions in a prohibitively large search space and, in the case of MANETs, reduce the computational complexity needed for a node to determine its next location.
Structural parameterizations of hard graph problems
Year of Dissertation:
2011
In traditional computational complexity we measure algorithm running times as functions of one variable, the size of the input. Though in this setting our goal is usually to design polynomial-time algorithms, most interesting graph problems are unfortunately believed to require exponential time.
LIGHTWEIGHT 3D MODELING OF URBAN BUILDINGS FROM RANGE DATA
Year of Dissertation:
2011
Laser range scanners are widely used to acquire accurate scene measurements. The massive point clouds they generate, however, present challenges to efficient modeling and visualization. State-of-the-art techniques for generating 3D models from voluminous range data is well-known to demand large computational and storage requirements. In this thesis, attention is directed to the modeling of urban buildings directly from range data. We present an efficient modeling algorithm that exploits a priori knowledge that buildings can be modeled from cross-sectional contours using extrusion and tapering operations. Inspired by this simple workflow, we identify key cross-sectional slices among the point cloud. These slices capture changes across the building facade along the principal axes. Standard image processing algorithms are used to remove noise, fill holes, and vectorize the projected points into planar contours. Applying extrusion and tapering operations to these contours permits us to achieve dramatic geometry compression, making the resulting models suitable for web-based applications such as Google Earth or Microsoft Virtual Earth. This work has applications in architecture, urban design, virtual city touring, and online gaming. We present experimental results on the exterior and interior of urban building datasets to validate the proposed algorithm.
STRUCTURE-BASED SEARCH TO SOLVE CONSTRAINT SATISFACTION PROBLEMS
Year of Dissertation:
2011
Constraint satisfaction is a paradigm that applies to many challenging real-world tasks with direct practical relevance, such as planning and scheduling. It models these tasks as constraint satisfaction problems (CSPs) and then solves them with search. Compared to artificially-generated CSPs, real-world CSPs are more likely to have non-random structure. This dissertation shows the difficulties encountered by traditional and state-of-the-art search techniques when the structure of such a problem is overlooked. Here, a novel hybrid search algorithm for CSPs combines two fundamental search paradigms (global search and local search) to solve structured CSPs. It first uses local search to detect crucial structure (the structure identification stage), and then applies that structural knowledge to solve the problem by global search (the search stage).
Efficient Processing of Very Large XML Documents in Small Space
Year of Dissertation:
2012
The focus of this research was to develop a highly efficient serialized data structure for use in Document Object Model (DOM) query systems of Extensible Markup Language (XML) documents, which are increasingly the dominant model for data representation across the World Web. The space efficiency of the serialized data structure developed is shown to improve query response time and eliminates the need to rebuild the DOM representation each time it is desired to query an existing XML document. Moreover, this serialized data structure enables DOM modeling of extremely large XML documents at a low and fixed memory cost. New algorithms and software tools for working with these data structures have been developed and this allows for compatibility with standard DOM modeling. The structures, tool and techniques presented can be readily adapted for use on the Semantic Web as it becomes a more prominent feature of the internet.
A Tiling Approach to Producing High Quality Solutions to Real World Timetabling Problems
Year of Dissertation:
2011
The problem of constructing timetables in a fast and efficient manner is faced by a wide variety of scheduling practitioners. These timetables may specify the weekly calendar of university courses for a semester or contain the dates and times of games for a sports league. Current areas of research in timetabling have focused on problem instances that are small and often not representative of the real world challenges. Hence, the solution approaches proposed often do not solve the needs of the scheduling practitioner.
2D DIctionary Matching in Small Space
Author:
Shoshana Neuburger
Year of Dissertation:
2012
The dictionary matching problem seeks all locations in a given text that match any of the patterns in a given dictionary. Efficient algorithms for dictionary matching scan the text once, searching for all patterns simultaneously. There are many scenarios in which storage capacity is limited or the data sets are exceedingly large. The added constraint of performing efficient dictionary matching using little or no extra space is a challenging and practical problem. This thesis focuses on the problem of performing dictionary matching on two-dimensional data in small space. We have developed the first efficient algorithms for succinct 2D dictionary matching in both static and dynamically changing data. Although time and space optimal dictionary matching algorithms for one-dimensional data have recently been developed, they have not yet been implemented. Since our two-dimensional algorithms employ one-dimensional dictionary matching, we created software to solve one-dimensional dictionary matching in small space. This is a first step towards developing software for succinct dictionary matching in two-dimensional data.
AUTOMATED AUCTION MECHANISM DESIGN WITH COMPETING MARKETPLACES
Year of Dissertation:
2011
Resource allocation is a major issue in multiple areas of computer science. Auctions are commonly used in optimizing resource allocation in these areas, since well designed auctions achieve desirable economic outcomes including high allocative efficiency and fast response to supply and demand changes.
Computer-Aided Reasoning about Knowledge and Justifications
Year of Dissertation:
2009
The dissertation consists of two Chapters.