Research Activies and Interests
My research at UIC in the Artificial Intelligence Laboratory
has focused on developing efficient artificial intelligence (AI) search techniques. This research has two components: basic research into developing general, efficient heuristic search algorithms, and applied research and development using heuristic search and other AI methods to solve problems in the areas of transportation, manufacturing, bioinformatics and high-availability computer clusters.
General Techniques for Improving Search Efficiency
One of our most interesting results in this area has been the development of a new heuristic search algorithm named perimeter search
. This admissible technique is referred to as perimeter search since it relies on a perimeter of nodes around the goal or destination node. During the search process, generated nodes are compared to the perimeter nodes. When a match is found, the search can terminate. Analytical and experimental results were published in the Artificial Intelligence Journal showing that perimeter search is more efficient than IDA* and A* in terms of time complexity and nodes expanded for two problem domains. Additional general search results have been in the area of search algorithms that learn; a method for reducing cycles for depth-first searches on graphs; and parallel bidirectional search algorithms.
Intelligent Transportation Systems
Our Intelligent Transportation Systems (ITS) research involves improving the utilization and efficiency of existing roadway transportation systems using information technology. From 1991-95, I conducted ITS research for the ADVANCE (Advanced Driver and Vehicle Advisory Navigation ConcEpt
) project, supported by the Illinois Department of Transportation and the Federal Highway Administration (FHWA). ADVANCE equipped test vehicles in the northwestern suburbs of Chicago with on-board computers for dynamic route planning and navigation. The vehicles received real-time traffic information via RF communications from a traffic information center, allowing them to plan and update optimal routes using up-to-the-minute traffic information. The traffic information center received traffic information from the vehicles, acting as roving traffic probes, as well as from roadway loop detectors, reliable voice reports, and other sources. My laboratory’s responsibilities on the ADVANCE project were for software research and development for the traffic information center.
I have also conducted several other ITS-related projects. In 1994-95 my Laboratory developed a regional Corridor Traffic Information Center for IDOT that included the first World Wide Web site to graphically display current traffic conditions, see www.gcmtravel.com/gcm/maps_chicago.jsp
for details (The CALTRANS WWW traffic map was also developed around the same time.) Our traffic map web site has over 300,000,000 hits per year. Another project, funded by the National Research Council’s Transportation Research Board, has developed powerful new data fusion techniques utilizing artificial neural networks. Reliable data fusion is critically important for advanced traveler information systems, which must continually combine semantically distinct probe, loop detector, anecdotal, and historical data into meaningful current traffic information. Another project, initiated by the FHWA and the Illinois, Indiana, and Wisconsin Departments of Transportation, involves the research and development of a transportation information center for the vital Gary-Chicago-Milwaukee Priority Corridor, one of the four federally-designated ITS testbed corridors. This system distributes real-time transportation and incident information throughout the corridor to agencies and the traveling public. My laboratory has also been awarded contracts to assist the Illinois Tollway Authority with the development of a state-of-the-art traffic and incident management system, and a project with the Chicago Area Transportation Study (CATS) to development an intelligent web-based ridesharing system. Additional projects include work on an incident information system for the State of Wisconsin and transit projects funded by the Federal Transit Agency through the Great Cities Universities Consortium and the Regional Transportation Authority.
Additionally I am currently serving as a co-PI on a $3.2 million NSF IGERT
grant (Computer Science Professor Ouri Wolfson, P.I.) in the area of Computational Transportation Science involving four UIC colleges, for more information see cts.cs.uic.edu
Manufacturing Optimization and Knowledge Discovery
Manufacturing optimization, modeling, and knowledge discovery research has been supported by Motorola for the last ten years. This work involves optimizing the assignment of components to the feeder slots of high-speed "chip shooters" (devices which place IC chips onto printed wire circuit boards) in a high-mix manufacturing environment. A variety of AI methods (e.g., genetic algorithms, tabu search, neural networks, and rule-based systems) have been utilized to consistently produce near-optimal results for high-speed placement over a wide class of machines. The methods and software we have developed are currently being used in Motorola factories around the world. This work has included balancing and optimizing a complete assembly line and generalizing our machine specific work into a flexible simulation and optimization toolkit. Extensions to this work include the development of the data mining software for design and manufacturing, and meta-knowledge extraction and management for SMT optimization.
Computational Biology and Bioinformatics
Bioinformatics research has been funded by the National Institutes of Health National Center for Human Genome Research to develop a DNA restriction mapping tool. This tool automates the process of inferring DNA restriction maps from DNA segmentation data. We have studied the utility of certain AI techniques in this domain, namely Pratt's separation theory (to guarantee optimal use of the data), Dempster and Shafer's theory of evidence (for reasoning with uncertain data), and heuristic search guided with neural networks to traverse the search space efficiently. Our restriction mapping tool has been downloaded by numerous molecular biology laboratories around the world from our homepage.
More recent efforts have focused on using data mining for understanding the mechanisms of evolution and adaptation of organisms to the environment by identification of evolutionary variations of enzymes using advanced data-mining approaches. Protein classification is an important method for automated protein function prediction.
In 2006 and 2007, I also served as one of the seven founding board members for the Chicago Biomedical Consortium Proteomics and Informatics Scientific Board
, in response to a $25 million biomedical research gift from the Searle Funds given jointly to UIC, University of Chicago and Northwestern University.
High-Availability Computer Clustering
Work in the area of highly available computer clustering has been supported by Sun Microsystems and the National Science Foundation. High availability (HA) in a cluster is achieved through redundancy; all critical resources have designated redundant resources that can take over the service responsibilities of the original resource in case of a failure. Our work involves applying constraint logic programming (CLP), rule-based systems and heuristic search techniques to the configuration and failure handling in HA clusters.