RESEARCH SETTING

[Research Setting] [Research Administration] [Research Funding and Awards
My current research interests center around
    Artificial Intelligence (AI):
      General: Search, Knowledge Representation (KR), Games, Strategies, Concurrent Systems, Accuracy and Complexity of AI Algorithms, Formal Languages for KR, Machine Learning; Specific: Linguistic Geometry, with applications to Concurrent Multiagent and Distributed Systems, Automated Reasoning, Robotics, Combat Simulation, Aerospace Control, Scheduling, Manufacturing, Software Re-engineering, Network Security, Machine Learning, etc.
    Software Engineering:
      Software Development Environments, Teamwork Support, Software Maintenance, Software Testing, High Assurance Systems, Software Re-engineering.


Since 1972, for 16 years I worked with Professor Mikhail Botvinnik, Former WorldChess Champion, in Moscow, Russia. It was called a PIONEER project for the USSRState Department of Science and Technology and Department of Energy. The goal ofthis research was to learn and implement as computer programs a methodology ofthe most advanced chess players of solving chess problems almost without search,and then apply this approach to the wide spectrum of complex practical problems.The research team had two subjects for investigation: advanced experts (likeBotvinnik himself) and computer programs, computer chess program PIONEER and anumber of planning and control heuristic programs. The permanent feedback fromboth resulted in constant rethinking, multiple redevelopment of the algorithmsand the programs. This was an exciting learning and research experience.Researchers from around the world were coming to Moscow to observe results ofthis team.

The results of the PIONEER project and other projects I was involved in werebased on the investigation of sophisticated human heuristics resulting in highlyselective searches, on integration of experimental and theoretical approaches.This research experience and mathematics/computer science background helped me tomake generalizations, taking into account theoretical concepts which seemed to beunrelated to the main problem. Since 1980, I am developing theoreticalfoundations of those projects. Since 1990, this approach is called LinguisticGeometry (LG). A reason for this name is the geometrical nature of discoveredheuristics and the mathematical tools of the theory of formal languages used toformalize them. The name, LG, first appeared as a title of my invited talk givenat the University of Quebec at Montreal, Canada in 1991, and then as a title ofthe abstract of my paper in the Abstracts of the Second International Symposiumon Artificial Intelligence and Mathematics, Fort Lauderdale, FL, Jan. 1992.

The following development of LG showed that the power of this approach goes farbeyond original chess problem domain. It is applicable to numerous military andindustrial concurrent multiagent systems, including vehicles routing, intelligentmanufacturing, robot control, high assurance hardware/software systems, spacenavigation, network security, etc. This research gives new mathematical tools forrepresentation and reasoning about abstract images extracted from the expertvision of complex control problems. The syntactic tools allow us to decomposeconcurrent multiagent system into the dynamic hierarchy of subsystems, ahierarchy of the networks of paths, and solve otherwise intractable searchproblems by reducing the search dramatically (e.g., from trillions to tens ofstates).

Research on LG requires significant experimental efforts and theoreticaladvances.

Experimental research includes development and investigation of various LGapplications. A number of prototypes of LG systems and commercial products weredeveloped at Lockheed Martin Corp., GIS Solutions, Pioneer Technologies, SandiaNational Laboratories, Rockwell Science Center, University of Colorado at Denver,and University of Denver. The most direct application of LG is the application tocombat simulation problems. The first software prototype of the LG combatsimulation system for unmanned aerial vehicles (UAV) was developed at PhillipsLaboratory, Kirtland Air Force Base. A number of LG prototypes were developed atthe University of Colorado at Denver. An extensive work is conducted at RockwellInternational Corp. Recently, a prototype of the Combat Simulation Tool has beendeveloped by the joint efforts at the University of Colorado at Denver and theUniversity of Denver. A pilot version of this program was demonstrated at theSecond Symposium on LG in Berlin, Germany in1997. An advanced version will bedemonstrated at the Third Symposium on LG at San Diego in October of 1998.

Theoretical research includes investigation of computational complexity, formalcorrectness, and accuracy of the LG algorithms. The specific direction isdevelopment of the generic theory as well as consideration of the specificclasses of problems based on a number of experiments with LG applications.Redevelopment of LG foundations, LG grammars, expansion of LG to multiagentproblems variable mobility are some of the current topics. In particular, arecent fascinating result is the proof of global optimality of the solutionsgenerated by LG algorithms for a classes of search problems. This result wasreceived about two years ago but its value became apparent just recently. Ittells that LG algorithms (basically algorithms that simulate methodology of themost advanced human experts) generate optimal solutions with almost no search.Optimality means that the result is the same as the solution to be received afterexhaustive search (which is practically non-doable). This proof itself sparked anew direction in LG: solving search problems by construction of strategieswithout search at all. A prototype of the Combat Simulation Tool mentioned aboveis the first implementation of the new no-search approach.

Since 1991 when this term, LG, was coined, 19 journal papers on LG have beenpublished or accepted for publication. The total number of refereed papersdealing with LG and related issues is about a hundred. Currently, I am workingon a special issue of the journal devoted exclusively to LG. I completed aresearch monograph ŚLinguistic Geometry: From Search to Constructioną to bepublished by Kluwer Academic Publishers in 1998.
[Home]