THE SPIRIT OF THE TUTORIAL
How can human expert heuristics, which where successful in a certain class of search problems, be transferred to different problem domains? What language tools can be applied to the area of successful results in order to generate a formal, domain independent knowledge ready to be transferred?
This tutorial is intended to introduce researchers, practitioners and graduate students to the main ideas and results of research on geometrical properties of complex multiagent systems, the so-called
Linguistic Geometry. The purpose of Linguistic Geometr
y is to accomplish applications to space navigation, robotics, planning, scheduling, VLSI design and other systems. This research includes the development of syntactic tools for knowledge representation and reasoning about large-scale hierarchical complex systems. It relies on the formalization of search heuristics of
highly-skilled human experts that have resulted in the development of successful applications in different areas. It is based on broad application of the theory of formal languages and gramm
ars as well as theories of formal planning employing first order predicate calculus. The syntactic tools allow us to decompose complex concurrent system into the dynamic hierarchy of subsystems, the networks of paths, and thus solve intractable problems of simulation of multiagent environment by reducing the search dramatically (e.g., from billions to tens). The results in theory and applications to robotics, space navigation, and scheduling will be presented. More details are given in the
Summary of Contents.
Linguistic Geometry elicited a keen interest of researchers and practitioners, and, in particular, at aerospace and defense funding agencies. Professor Stilman has given numerous contributed, invited, conference and tutorial presentations of this approach literally around the world. Just in September 1994, within one week he traveled to Australia and then directly to Luxembourg to give invited 3-hour presentations of Linguistic Geometry at conferences to the large audiences. Also, during last two years 10 journal papers (including invited papers) on Linguistic Geometry have been published or accepted for publication. Professor Stilman organized the First Symposium on Linguistic Geometry and Semantic Control together with the Center on Optimization and Semantic Control (Washington University, St. Louis). This Symposium was held in Puerto Rico in February 1995.
Linguistic Geometry has many points for research and applications. This Tutorial should cause the dissemination of the main ideas, which would be followed by new results in theory and applications.
WHO SHOULD ATTEND
There is no doubt that you have been challenged repeatedly trying to solve search problems of very high dimension in your business activities. Probably, you was buried by the astronomical number of different variations hiding a solution. But you managed to solve these problems. Maybe not always. There are many such problems, very important problems, like robotics control, aerospace navigation, or network management problems that are hardly manageable or not manageable at all. You should learn about new very efficient approach to this class of problems, about new cutting edge developments in Artificial Intelligence. Then you would be able to apply and adopt this approach to solving your most important tasks. Do not miss this opportunity to keep yourself up to date in this rapidly developing area without reading confusing research papers and scary thick monographs.
Basically, all the required preliminary information will be given in the Tutorial.
SUMMARY OF CONTENTS
Linguistic Geometry
T U T O R I A L Boris Stilman Department of Computer Science & Engineering University of Colorado at Denver, USA 1. Introduction to heuristic networks for the complex systems control. 1.1. Experimental background: scheduling, planning and game playing heuristic programs. 1.2. Optimization problems for autonomous agents on surface and in space. 1.3. Artificial agents in scheduling. 1.4. Search reduction examples: informal survey. 2. Introduction to mathematical tools: hierarchy of formal languages. 2.1. Formal languages and grammars (a brief survey). 2.1. Controlled grammars 2.2. Generating techniques 2.3. Examples of generation. 3. Class of problems. 3.1. Definition of Complex System. 3.3. Complex Systems: autonomous agents in robotics, scheduling, positional games. 3.3. Measurement of distances in Complex System. 3.4. Flexible Computation: Horizon 4. Representation of paths: Language of Trajectories. 4.1. Shortest path: shortest trajectory, generating grammar, constraints. 4.2. Obstacles and roundabout path: admissible trajectory, generating grammar, constraints. 4.3. Trajectories in robotics and resource scheduling. 5. Representation of networks of paths: Languages of Trajectory Networks. 5.1. Trajectory connection. Family of Network Languages. 5.2. Language of Zones: semantics, generating grammar, Zone of robotic vehicles. 5.3. Zones as trajectory networks. 6. Representation of motion: Translation of languages. 6.1. Translation of Languages of Trajectories. 6.2. Translation of Languages of Zones. 6.3. Representation of changed and unchanged networks: translation kernel. 7. Representation of search: Languages of Searches. 7.1. Efficient search control in the Language of Translations. 7.2. Search control grammars. 7.3. Translations grammar. 8. Applications of Linguistic Geometry 8.1. Search reduction in 2D problems: robotics, scheduling, air combat. 8.2. Search reduction in 3D problems: aerospace navigation. 8.3. Search reduction in the problems with concurrent motions: 2D and 3D combat. 9. Future directions. 9.1. Optimality of the solutions. 9.2. Computational complexity of the grammars.