The first one is the Center for Optimization and Semantic Control at Washington University, St. Louis, MO. This Center, directed by Professor Ervin Rodin, is involved in the development of the new discipline called Semantic Control (SC). Semantic Control deals with the synthesis of solutions to control problems that do not lend themselves to formulation and analysis via classical methodologies. They are mostly of defense nature in the form of multiagent pursuit-evasion games. Common to all is the use of a multi-disciplinary approach, using systems theory, artificial intelligence, operations research and computational methods. Researchers of this Center consider Linguistic Geometry as one of the most worthwhile tools to attack problems in Semantic Control. In particular, I have been invited to St. Louis to teach an advanced short course on LG. Professor Rodin as Editor-in-Chief of the journal Computers and Mathematics with Applications invited me to submit papers on LG to this journal. To date, five substantial papers on LG have been published or accepted for publication in this journal. The draft versions of those papers can be retrieved from these pages. Researchers of this Center served as co-organizers and active contributors of the Symposium on LG & SC. I take this chance to thank Professor Rodin, Al Garcia, and Mike Meusey for their efforts and excellent contributions. Two papers on Semantic Control are included in the Proceedings.

The second research institution is the Mathematical Sciences Institute (MSI) at Cornell University, Ithaca, NY. This major Institute directed by Professor Anil Nerode is involved in different research projects. As a result of the present collaboration with Dr. Vladimir Yakhnis we expect to extend the application domain of LG to the area of verification of concurrent systems such as parallel programs and to the operating systems supporting persistent truly concurrent objects. I also expect that LG would have extensive applications to the so-called Hybrid Systems, being developed at MSI. Our collaboration will generate a new, deeper understanding of the Foundations of LG, and, eventually, will explain theoretically the efficiency of LG applications. Researchers from MSI plan to invite me to MSI to give a talk on LG. Dr. Vlad Yakhnis contributed to the Symposium on LG through our joint paper on Foundations of LG , and I would like to thank him for the excellent job.

LG can be distinguished from other AI approaches by its tremendous computational power. Experiments comparing the AI systems based on LG and those utilizing other approaches (e.g., search algorithms with alpha-beta pruning) have shown the former to be superior. Some of the problems were not solvable by other approaches at all, whereas LG systems successfully solved them. For other problems both the branching factor (the average number of moves in each node) and the computation time for the systems based on LG were several times smaller than those for the competition.

The first pilot implementation of the elements of the generic hierarchy of formal languages for the 2D-space case was done at the University of Colorado at Denver in 1993, by King and Mathews employing CLIPS tools and C language, respectively. They developed a working prototype of an advanced LG system. We applied this prototype to the problem of optimal control of four robotic vehicles participating in a two-player game in a 2D space. Basically, the problem was represented as four aircraft in a discrete event pursuit-evasion game in the on-surface projection. Theoretical results employing conventional approaches and experiments with programs utilizing these approaches show that search trees generated in order to solve this problem consist of more than a million moves with the branching factor around 6. The LG tools allowed us to find the optimal solution generating the search tree which consists of only 56 moves, whereas the branching factor is very close to 1 (1.65). The low branching factor means that the algorithm is actually goal-oriented, i.e., it approaches the goal almost without branching.

An even more interesting result involved solving a similar problem of optimal control of robotic vehicles but for a 3D case. The problem was represented as a pursuit-evasion game of space ships and space stations. The conventional approaches require a billion move search tree to solve it, while the tree generated by LG consists of about 50 moves and is very similar to the tree from the 2D example. On the basis of the complexity of the hierarchy of languages which represents each state in the process of the search, one may be driven to conclusion that the growth from the 2D case to 3D is linear (with the factor close to one). This means that the complexity of the entire algorithm may be about linear with respect to the length of the input which is amazing.

In a new paper Multiagent Air Combat with Concurrent Motions , included in the Proceedings of the Symposium, I managed to relax one of the most restrictive requirements imposed on the autonomous agents (BOMBERS, FIGHTERS, SPACE STATIONS, and so on). This was the requirement inherited from the positional games, the testbed of Linguistic Geometry, that only one agent at a time can move. This requirement was the object of criticism by some of the researchers. Obviously, for the real world problems it is very important that the agents could move simultaneously. The general tools of Linguistic Geometry never required this constraint but I did not have software prototypes and meaningful examples with simultaneous motions. Now such an example has been developed. All the agents of each side can move simultaneously if necessary. This example demonstrates even greater advantage of the Linguistic Geometry tools. Because of the allowance of concurrent motions the number of legal moves in each state grows significantly, since all the combinations of legal moves are allowed. This number causes the tremendous growth of the state space. As usual, the total size of the state space grows exponentially (with the branching factor as a base). It is hard to believe this but the search tree generated by the Hierarchy of Languages (theoretically) does not grow at all! The search reduction achieved in this example is even more dramatic than it was before. This needs to be confirmed by the software prototype to be developed.

Another paper entitled Deep Search in Linguistic Geometry contains a 2D example of optimization problem of aerospace combat with 8 agents involved. The moving capabilities of some of these agents are far more advanced wi th respect to the previously published examples of LG applications. The depth of the search tree required to solve this problem must be at least 25 moves. Taking into account that the unreduced branching factor for the problem is around 15 we conclude tha t the search tree should contain 15²⁵ moves, which makes this problem untractable employing conventional approaches. LG tools allowed to solve it by generating a search tree of 150 moves with the branching factor 1.12!