Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Linguistic geometry : from search to construction
Stilman B., Kluwer Academic Publishers, Norwell, MA, 2000. 395 pp. Type: Book (9780792377382)
Date Reviewed: Jan 1 2001

Stilman’s provocative title highlights a contrast that permeates artificial intelligence, and, in fact, computer science in general. Geometric representations cast problem solving as a search through a space, and linguistic representations construct solutions by executing the rules of a generative grammar. In the best spirit of creative research, Stilman outlines a deep and powerful synthesis of these two perspectives, and persuasively shows its capabilities on a wide range of problems.

Linguistic geometry (LG) is the outgrowth of Stilman’s own personal and scholarly pilgrimage, beginning with his research in Moscow with Mikhail Botvinnik, a world chess champion, on computer methods for playing chess. This led to a number of metaphors that pervade LG: the representation of space as a playing board, of agents as pieces that move over this playing board, of interactions among playing pieces according to a set of rules, and even of general problems as instances of classical chess endgames. By the end of the book, the playing board is no longer two-dimensional, regular, or even restricted to physical space; the pieces can move concurrently; and the rules can vary over time. The informal notion of a board game becomes a formal object, the “complex system,” described as an eight-tuple made up of a finite set of points; a finite set of elements that can be located at those points (partitioned into two disjoint subsets representing opposing sides); a set of reachability relations describing where a given element located at a given point can move next; a function on the set of elements, describing their values; a state space, whose elements record the placement of elements on points and other problem-specific information; a set of starting states; a set of target states; and a set of transitions, each consisting of a rule whose condition is a pattern on the system state and whose actions include assertions to be removed from and added to the state when the rule fires.

The linguistic side of LG stems from the extension of linguistic methods to pattern languages. The objects described by these languages are the trajectories of agents over their generalized game board, or complex system. Stilman develops these languages as a hierarchy with three levels.

The lowest level is made up of languages of trajectories, which describe the set of all paths between points of a complex system. Trajectories are constructed using the reachability relations in the complex system. Multiple trajectories of different lengths may exist between two points, and the languages of trajectories include definitions for the length of a trajectory and ways of recursively defining an admissible trajectory in terms of shortest trajectories. Intuitively, this level of languages permits the description of the movement of a single element over the set of points.

Trajectories form the alphabet for the second level of the LG hierarchy, languages of webs, which capture a snapshot of the relationships among multiple elements at one point in a game. This level includes concepts for the relationship between two trajectories; zones bounded in spatial extent and in time; and characterizations of zones in terms of the intent of the interacting elements, such as attack, block/relocation, domination, retreat, and unblock. Each state of the system corresponds to a single language at this level, and translations between successive trajectories and successive zones capture the temporal evolution of the interactions.

Those languages of translations form the third level of the hierarchy. The point of the book’s subtitle, “from search to construction,” is that searching in the conventional sense is replaced by construction of a single string in the language of translations. The amount of conventional searching that takes place is extremely restricted. For example, one early example deals with a problem whose brute-force search tree has a depth of 13 with nine possible moves at each node, yielding more than 1012 possible moves. Application of conventional heuristics, such as minimax search with alpha-beta pruning, still must consider more than a million moves. Yet LG finds a solution by generating a tree with only 46 moves, corresponding to an effective branching factor of 1.17 instead of the original nine. For a subclass of problems, the method is even more efficient, permitting construction of the complete solution with no searching at all.

The book’s organization makes the basic results quickly accessible, while providing detailed information as needed. After an introductory chapter that situates the methods historically, chapter 2 outlines the complete formal hierarchy of languages. Chapter 3 applies the methods to robotic combat in two dimensions. Chapter 4 moves to three dimensions, chapter 5 introduces more complex agents with more options, and chapter 6 introduces concurrency. While the board game analogy is most naturally applied to combat problems in physical space, chapter 7 illustrates how a more conventional optimization problem, such as scheduling a power grid, can be cast in this framework. Each of these first seven chapters takes a successively deeper look at the overall system. Chapters 8 through 14 consider particular details of the system in more depth, including generating techniques, specific languages at different levels, and the computational complexity of LG. Chapter 1 is intrinsically historical, and each of the other chapters concludes with historical remarks that trace the development of the concepts discussed in that chapter. These autobiographical glimpses offer a fascinating example of how a technique originally developed in a constrained context (computer chess) can be applied much more broadly. The book concludes with a comprehensive bibliography and index.

Reviewer:  H. Van Dyke Parunak Review #: CR124056
Bookmark and Share
  Featured Reviewer  
 
Multiagent Systems (I.2.11 ... )
 
 
Games (I.2.1 ... )
 
 
Graph And Tree Search Strategies (I.2.8 ... )
 
 
Grammars And Other Rewriting Systems (F.4.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Multiagent Systems": Date
Engineering intelligent hybrid multi-agent systems
Khosla R., Dillon T. (ed), Kluwer Academic Publishers, Norwell, MA, 1998. Type: Book (9780792399827)
Aug 1 1998
 Transactional agents: towards a robust multi-agent system
Nagi K., Springer-Verlag New York, Inc., New York, NY, 2002.  205, Type: Book (9783540430469)
Apr 13 2004
CLOVER: an agent-based approach to systems interoperability in cooperative design systems
Zhao G., Deng J., Shen W. Computers in Industry 45(3): 261-276, 2001. Type: Article
Nov 20 2002
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy