The purpose of Linguistic Geometry is to provide solutions to a variety of problems with huge state spaces, where it is desirable to find optimal or suboptimal behavior of entities generating purposeful transitions from state to state. Such problems include cooperation/competition of teams of intelligent (or human guided) robots (e.g., for ground or seagoing vehicles, aircraft, or spacecraft); safety critical control systems for the remote fully automatic objects like planetary exploration vehicles, and space combat; VLSI design; planning, scheduling, and resources distribution; chess, etc. Traditionally, finding optimal or suboptimal behavior of entities for the above systems, required searches for suitable branches in giant "search" trees. Such searches are often beyond capabilities of modern and conceivable future computers. Dr. Stilman's approach dramatically reduces the size of the "search" trees, thus making the problems computationally tractable. Although discrete by its nature, this approach could also be applied to control of continuous plants described by ordinary or partial differential equations, albeit after a discretization of the equations.
One of the distinguished features of Professor Stilman's approach is the formalization and utilization of search heuristics developed by highly-skilled human experts (including chess grandmasters). These experts developed sophisticated and highly
successful strategies resulting in tremendous search reduction in their areas. However, before Dr. Stilman's work the methods behind the experts' heuristics and intuition were not understood or seen by the AI scientists or even by the experts themselves.
Using the theory of formal languages, geometrical insight, and the powerful apparatus of modern formal logic, Dr. Stilman was able to formalize and generalize these heuristics, thus enabling them to be applied to a vast class of problems. It is interesting to note that prior to Dr. Stilman's work, most of these problems were not included by the experts in the areas of applicability of their heuristics.
Dr. Stilman's work on the formalization and application of the experts' heuristics may be divided into three stages. In the mid-80s he created an initial model of the heuristics which mostly consisted of a collection of powerful algorithms. Numerous experiments were performed to compare the systems based on that initial model and systems utilizing other approaches (e.g., search algorithms with alpha-beta pruning). The experiments have shown that many problems, which were not solvable by the other approaches at all, have been successfully solved by Stilman's systems. Moreover, for the rest of the problems, Dr. Stilman's systems were proved to be significantly faster than the other approaches.
In the 90s , Professor Stilman unified and generalized his initial model by describing the principles of reducing the multitude of computations involved in dynamic management of states for complex state transition systems. Since both the formal languages and the geometry of the state apace were involved, the advanced second model of Dr. Stilman's approach was named Linguistic Geometry (LG). In retrospect, the previously developed part of Dr. Stilman's approach to AI is now being referred to as LG as well.
In 1993, a working prototype of an advanced LG system was designed (using CLIPS programming environment). It was applied to the problem of optimal behavior of four robotic vehicles in a 2-dimensional (2D) space participating in a two-player game.
The problem was represented as four aircraft in a discrete event pursuit-evasion game in the on-surface projection. Theoretical results employing other approaches and experiments with programs utilizing these approaches show that the search tree generated in order to solve this problem consists of more than a MILLION moves with the branching factor (i.e., the average number of moves in each node) around 6. In contrast, the LG tools allowed to find the optimal solution generating the search tree which consisted of only 50 moves, with the branching factor of 1.65 (i.e., close to 1). The low branching factor indicates that the algorithm is goal-oriented, i.e., it approaches the goal almost without branching.
An even more interesting result was obtained by solving a similar problem of optimal behavior of robotic vehicles but for the 3D case . The problem was represented as a pursuit-evasion game of space ships and space stations. The conventional approaches require a BILLION move tree to solve it, while the tree generated by LG consisted of merely about 50 moves with branching factor close to 1. On the basis of these experiments, one may be driven to conclusion that the growth from the 2D case to 3D is LINEAR (with the branching 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. In contrast, similar growth for other approaches is at least exponential.
Another significant test of LG methods involving a much larger state space was conducted in the form of a 2D pursuit-evasion game which involves 8 aerospace vehicles. Theoretical estimates and experiments with computer programs showed that finding a solution of this problem requires generation of the search tree that includes about 1525 moves. The depth of the search must be extremely big, at least 25 moves. To traverse such a search tree using other methods is beyond the reasonable time constraints of the modern computers. In contrast, the search tree generated employing the Linguistic Geometry tools consisted of just 150 moves. This suggests that the growth of input (the number of vehicles and their moving capabilities) practically did not cause growth of the search. The branching factor even has been reduced down to 1.12! Again, this suggests that the growth of the computational complexity for the LG models may be linear.
The work on the third stage of Dr. Stilman's approach started in the Fall of 1994. Together with Dr. V. Yakhnis he developed a new kind of games called multiagent graph-games with simultaneous moves. These new games permit simultaneous (CONCURRENT) moves of several cooperating/competing agents; moreover, each agent may either skip or move one or more pieces at the same time. The resulting fusion of the multiagent graph-games with simultaneous moves and LG created new directions for application of LG to multiagent systems possessing a high degree of concurrency.
In all the above examples, the pieces (i.e., aircraft, spacecraft, etc.) moved in a serial mode, one piece at a time. Moreover, the motions of the opposing sides were alternating. In the new example developed by Professor Stilman in 1995 and reflecting the third stage in the development of LG, the aircraft, both cooperating and opposing, can move concurrently. The example involves 2 opposing teams, 2 aircraft in each team. The introduction of concurrency results in a significant growth of the unreduced branching factor (up to 324). Although the depth of the search is merely 6, it still gives us a giant unreduced search tree of about 3246 moves (i.e., of the order of 1015). In contrast, the search tree generated by the LG methods for this totally concurrent model contains just 34 moves. Since the maximum depth reached is 6, the branching factor of this tree is 1.53. This is a tremendous reduction in comparison with a 1015 move tree that would have to be generated by the conventional search
procedures, or even with the theoretical minimum of the minimax search with alpha-beta cutoffs which is (1015)1/2 ~3*107.
Besides the problems with explicit moving entities and opposing agents (like combat simulation), the LG tools can be effectively applied to the scheduling problems with resources allocation by introducing artificial "board", moving "pieces", and opposing agents. This representation allows to solve a number of problems of very high dimension which are practically intractable employing conventional approaches.