Acta Polytechnica Vol. 43 No. 2/2003 A Multi-Agent Mah Jong Playing System: Towards Real-Time Recognition of Graphic Units in Graphic Representations H. Achten, J. Jessurun In arehíteetural design, sketehing is an important means to explore the first coneeptual developments in the design proeess. It is neeessary to understand the conventíons ojdepiction and eneoding in sketehes and dmwings ifwe want to support the arehiteet in the sketching aetivity. The theory ojgraphic units provides a eomprehensive list ojconventions ojdepietion and encodíng that are widely used among architects. These graphie units Jorm useJul building blocks to undmtand design drawings. We investigate whethn it is possible to build a system that can recognize graphic units. The technology we are looking at is multi-agent systems. ft was ehosen Jor the Jollowing reasons: agents ean speeialize in graphic units, a multi-agent system can deal with ambiguity through negotiation and confliet resolution, and multi-agent systems Junction in dynamically changing environments. CUTTently there is no geneml approach or technology availabLe Jor multi-agent systems. TkneJore, in our research we first set out to make such a multi-agent system. In order to keep the complexity low, we first aim to make a system tkat ean do something simple: playing Mah Jong solitary. The Mah Jong solitary system shares the Jollowing important Jeatures witk a multi-agent system that can recognize graphic units: (I) speeialized agents Jor moves; (2) negotiation between agents to establish the best move; (3) a dynamieally ehanging environment; and (4) searek activityJar more advanced strategies. The paper presents the tkeoretical basis ojgraphic units and multi-agents systems, Jollowed by a description ojthe multi-agent framework and its implementation. A number oj systems that ean play Mah Jong at various degrees oj competence and aecordingly degrees oj complexity oj multi-agent system, are distinguished. Finally, tke paper demonstrates how the findings are inJonnative Jor a system that can recognize graphic units. Keywords: AI, multi-agent systems, games, graphic units, architectural design. 1 Graphic units Graphic representations such as sketches, plans, sections, perspectives, and so forth are not only very personal docu­ ments because of style of drawing, bUl also can be used to share information between professionals. This share ability is possible because architects use well-established conventions of depiction and encoding. Conventions of depiction are types of images such as plans, sections, and elevations. Con- Table I: Graphic Units ventions of encoding are the line types and hatching patterns that provide further information about the drawing. In an analytical study of some 220 drawings taken from the thirteenth to the twentieth Century, twenty-four specific kinds of drawing elements with a well-established use and meaning to architects based on conventions of depiction and encoding were identified [ll. These kinds of drawing ele­ ments are termed "graphic units". They are Iisted in Table 1. Graphic Unit Description Simple contour Regular shape showing an outline. Contom Any irregular shape showing an outline. Measurement device Measure for establishing (relative) dimensions. Specified fonn Contour with specified dimensions. Elaborated structural comour Outline with structural detail. Complementary contours Composition of outlines. Function symbols Textual indication of function. I Zone Area with specific use or function. Schematic subdivision Schematic depiction of principal subdivision. , lrregular subdivision of area along coordinating lines.Modular field Refinement grid Grid with smaller module coordinated in another grid. Schematic axial system Schematic depiction of organization of axes. Axial system Organization of axes applied to building design. 28 Acta Polytechnica Vol. 43 No. 212003 Graphic Unit Description Grid System of modularly repeating coordinating lines. Thrtan grid Double grid based on two alternating modules. Structural tartan grid Thrtan grid with structural elemenrs. Element vocabulary Set of simple shapes depicting (interior) elemenrs. Structural element vocabulary Set of simple shapes depicting structural elements. Functional soace Outline combined with function indicator. Partitioning system Schematic depiction of a more detailed subdivision. Proportion system Diagram showing how proportions are derived. Combinatorial element vocabulary Precise relationships between particular elements. lCirculation system Principal layout of circulation. Circulation Layout of circulation applied to building design. The following observations can be made: l) Half of the 24 identified graphic units represent stmctur- ing devices (e.g., grid, zone, and axial system) rather than concrete building elements (e.g., contours, func- tional space, and circulation). This implies that architects have an extensive set of representations for organizing the design. 2) Graphic units vary from being schematic, indicating global organization or intention (e.g., contour, schematic subdivision, and schematic axial system), to being very specific and precise about the location and dimension of the elements that are depicted (e.g., elaborated structural contour, functional space, and circulation). 3) As graphic units are built up of fairly basic graphic enti- ties, it is often only possible to distinguish between graphic units on the basis of their meaning. Thus, inter- pretation suffers from ambiguity. After the set of graphic entities has been settled as a specific graphic unit, how- ever, the purpose and use are clear. 4) Graphic units encode things such as composition, layout, modularization, circulation, and interior in a graphic way. Therefore, even without additional explicit textual infor- mation, they convey information that is generally shared by the architectural community. Much of this information is encoded implicitly, but can be derived by examining the drawing. We propose therefore, that graphic units can form the basis for a visual language on which to build more sophisticated design support. 1.1 Graphic unit recognition The ultimate goal of the research work is to implement a drawing system that will interpret drawings on the basis of graphic units. We look at 'drawing in action' for two main reasons: (l) to provide support through the system as the designer is working, in a very short time span after the drawing actions; and (2) to use drawing actions as clues for recognizing graphic units [2], [3]. Related work falls in the category of CAD systems and sketch analysis. Computational work on interpreting drawings has focused mainly on bottom-up analysis fiom primitives to larger constr-ucts, for example in facades [4], or more complex shapes in plans [5]. Examples for graphic de- sign support are the Electronic Cocktail Napkin [6], Hyper- sketch and PHIDIAS [7], Netdraw [8], and EsQUIsE [9]. The sketch functionality and interpretation of EsQUIsE is particu- larly close to the current work. EsQUIsE interprets strokes in a graphic environment as contours, grids, and functional spaces, and builds a representational model on this. EsQUIsE lacks a well-founded basis of elements that can be considered for analysis and computational interpretation. Related research in sketching, aimed at identifying perva- sive structures, is less common. Do et al [l0] look at common- alities in sketches, in particular shorthands for drawing the same concepts; McFadzean's Computational Sketch Analyser [3] takes sketch-acting clues as indicators for the current status of the design process; Koutamanis I l] proposes a taxonomy of elements in sketches, breaking them down into organiza- tional units not unlike graphic units. Rodgers et al [12] note a number of mechanisms between sketches without providing a more refined set of criteria to track design development. The works in question corroborate the proposition that there are stable aspects in graphics that are widely shared among architects. The novel aspect in our research lies in the use of acknowledged graphic structures (i.e., graphic units) as a means for computational design support. 2 Multi-agent systems The research area of multi-agent systems came out of the research field of Artificial Intelligence and more specifically Disributed Artificial Intelligence. It acknowledges two basic observations: (l) most of intelligent activity can be considered as distributed in one way or anotheq and (2) the isolated symbol-processing approach seems to have reached the limits ofwhat can be achieved. Based on this, the notion ofan "agent" as a situated and autonomous entity capable of interacting with the world and other agents has gradually developed tl3l, tl4l, [5]. Since the capabilities of such a broadly defined agent range fiom the very simple to the complex [16], there is as yet no single definition ofwhat an agent is [7], [8], nor a firm theoretical basis for multi-agent systems [9]. Although the mainstream ofwork on multiagent systems usually conceives agents in humanlike terms, a number of researchers have proposed to apply the multi-agent approach ,q Acta Polytechnica Vol. 43 No. 2/2003 to the more cognitive functions of intelligent behavior [20], [21 J, [22]. Franklin [23] sums up such directions and identifies agents as a necessary building block for complex and in­ telligent behavior. We adopt this latter view as our basic approach for building a multi-agent system for graphic unit recognition. Research on multi-agent systems focuses not only on the capabilities of the agents themselves, but moreover on rea­ soning within groups as cooperating Ol' competitive individu­ als. lt is generally found, that conceived this way, multi-agent systems can function robustly in highly dynamic and unpre­ dictable environments, removing some of the brittleness of previous AI systems. 2.1 Agents and graphic unit recognition Important issues to address in graphic unit recognition in drawings concem ambiguities and inaccuracies in the drawing, and resolving conflieting interpretations between candidate graphic units in the drawing. Multi-agent systems seem appropriate for tackling these issues. To summarize: • An agent can specialize in recognition of one particular gTaphic unit, building on other agents that reeognize more primitive graphic elements (systems approaeh). • Agents may engage in conf1ict identifieation and resolu­ tion; this is neeessary to deal with ambiguity in a drawing. • Functionality is built piecemeal on top of existing agents, so that the system can be developed incrementally. • Agent-systems ean funetion in dynamieally changing envi­ ronments, where resolution is not always possible. Drawing eonstitutes sueh an environment. lt is for these reasons that we tum to multi-agent systems to implement a system that can reeognize graphie units. 3 Development strategy There are two main issues to be resolved for graphie unit reeognition: (l) to understand the dynamies of a multi-agent system; and (2) recognition algorithms for graphic units. In this paper we address the question of dynamics and cantral. The reason for this is to better assess the possible eontribution of multi-agent systems to the research on graphic units. This is further discussed in the next section. 3.1 Multi-agent system for MahJong ln order to understand the dynamics of a multi-agent system, we first make a system that ean do something simpler than graphie unit recognition; namely, playing Mah Jong solila!)'. Mah Jong is a game involving 148 bones that are staeked in a specific pattem. Bones eome in pairs that are distinguished by suit (e.g., bamboo, circ!es, Ol' season) and number (ranging from one to nine). The purpose ofthe game is to clear the board by taking away per move two bones that form a mateh beeause they are ITom the same suit and number, and that have no bones Iying to the left Ol' right ol' them (see Eg. I). In eomparison to design, MahJong is a toy problem. Vet it has some eharaeteristies that make it worthwhile to look at in the perspeetive of design problems: I) Although the game is fully determined and finite, the player does not have fulJ information because of the stack­ ing of bones. 2) Complieations ean oeeur that may be antieipated by study­ ing the current situation of the board. These ean impose eonstraims on possible draws. 3) If a partieular bone needs to be taken away, and eurrently does not have a mateh, then this leads to goal-driven seareh for other bones to be taken away. Fig. I: Mah Jong Initial Layout 30 Acta Polytechnica Vol. 43 No. 2/2002 4) At many points during the game , the player can choose between various draws of bones in a move . The choice has ro be made with incomplete information, and competing arguments. A multi-agenr sysrem for recognition of graphic units needs to balance search and recognition strategies; search for l"1i:q*.ho!er rhe $aphic unir inwhich the {ent is special_ ized is being drawn, and recognition for determlningwirether the graphic unit is actually presenr. This search is similar to _ but more complex than - the problem of detecting which move to make. Furthermore, negotiation about besi moves resembles negotiation between agents to settle into an inter_ pretation of the drawing. In both cases, the environment changes dynamically through rhe moves made by the player and the drawing actions of the architect. 4 Agent framework We established an agent framework for developing a multi-agent system. An agent in the framework has- input, output, and an internal state and processes that are closed to the outsideworld. The input part senses the world environ- ment and receives broadcast messages. The outpur parr ma- nipulates the world environment and broadcasrs messages. Agents operare independently. It is possible to instantiate any number of agents of a given type. The multi-agent,yrt.- i, multithreaded, having all the agents nrn continuously at the same time. As in this way it is nor possible to predetermine in which orderwhich agents perform their actions, the design of the agents needs to take this into account. We establish im- plicit control through rhe use ofbroadcasts. An agent reads the broadcasts and selects those messages that are relevant. The agent's implemenration is basically as follows: l) Wait for a message. 2) If the message is not interesting, go to l. 3) Do something with the message. 4) Send messages. 5) Interact with the environmenr (if the agent can manipulate). 6) Go to l. An observer agent is implemented as follows: l) Observe the environment. 2) Broadcast a message about important changes. 3) Wait for a while. 4) Go to l. 5 The Mah Jorg system For the MahJong system, the core system contains three objects: Agent, Message Queue, and Message. The MahJong Solitary system is implemented using this core. The sysrem that plays Mah Jong starts from a configuration of simple agents, and is stepwise improved by adding agents thar can perform more reasoning. This phased approach is chosen so that it is possible to determine the influence on effectiveness and speed of different kinds of agents. The different systems, called Level 0, I, II, and III, are described in the followins sections. 5.1 Leael0 MahJong system The Level 0 Mah Jong System consisrs of three types ofagents: achooser that picks a random bone in the layout. a matchzr which checks if the chosen bones form a mati\, and a nwiler which removes the pair when the bones can be removed. The system needs at least 2 choosers in order to func_ tion; more cioosers increase system speed. Becau se the chllsers pick any bone in the layout, many of which cannor be drawn because they are not fiee, it typically takes many hours before the game terminates. The Level 0 system can terminate pre_ maturely by taking away a matching pair that blocks a fuiure pair of bones. The system has no means of detecting whether the game has blocked or ended. 5.2 Leael I MahJong system . The Level I MahJong System functions on rhe principle that it takes as a move the first match it finds. It consists of three types ofagents: afree agentthat broadcasts all the bones that are fiee for taking, a matrher that broadcasts all possible matches among the free bones, and am,oaer which removes the first match that the matcher finds. Compared with the Level 0 system, this sysrem speeds up the game-play by only looking at free bones. The Level I system can terminate prematurely for the same reason as the Level 0 system. The sysrem ends playing when the fiee agent can find no more free bones. ny checking whether this state occurs with the state that there are no more bones in the layout, the system can determine whether the game has been successfully completed or not. 5.3 Leael II MahJong system The level II MahJong Sysrem looks at all possible current matches and tries to choose the best match without reasoning about future states of the layout. Compared to the Level I system, it has an additional type of agent heuristic agents for deciding about the best move. A heuristics agent knows one game-playing heuristic. If there are more heuristics, then there are more agents, which have to decide among them- selves which heuristic prevails in the current move. The mover now removes the match of the winning heuristics agent. The choice for best match is based on the following heuristics: o Remove two fiee pairs: if it is possible to remove two pairs of a particular suit and number, then do so (thus, all four bones of a suit and number are removed). o Make long rows short: prefer a draw thatwill shorten a long row above a draw from a shorter row. r Remove high stacks: a stack occurs when two or more bones are stacked on each other. This heuristic prefers a draw that will make a high stack lower above a draw from lower stacks. If none of the heuristics apply, or if the result betr,veen the heuristics agents is a draw, then the system functions like the Level I system and the mover takes the first match found fromruthher. Compared with to system Level I, performance should improve, as the system is better able to avoid bad decisions. By allowing the heuristics agenrs to establish among them- selves a rank ordering (based on many mns and performance 3l Acta Polytechnica Vol. 43 No. 2/2003 comparisons) the system can detect which priority ranking gives better performance. The current listing above retlects the initial rank ordering. The system can terminate prematurely, for example by overlooking a blocking pair that is not in the current set of possible moves. From testing it has to be determined whether such cases will occur less frequently with the addi­ tionaI heuristics agents than in systems level Oand 1. 5.4 Level III MahJong system The Level III Mah Jong system not only looks at current best moves, but also reasons about future states of the board. The following heuristics agents are added: • Avoid leaving blocking pairs on the board: if there are two closely Iying bones of the same suit and kind in the same row, then efforts should be directed to remove at least one bone of this blocking pair. • Hindsight; confidence in a draw may be strengthened because of its consequences: (1) A bone has been freed that is necessary to unblock a row (thus removing a blocking couple); (2) the same bone as the removed match appears (that bone would never have been freed in another draw). • Maximize the number ofnew free bones: a draw can result in zero to six new free bones that can be candidates in the next draw. The current draw should maximize the number of free bones. • Longest chain: for each draw it is possible to estimate how many following draws can be made by looking to see which bones will become free. Choose the draw with the longest chain of possible moves. As in the Level II system, the heuristics agents can estab· lish an internal rank ordering. The current list above ref]ects the initial rank ordering. Testing has to determine whether system Level III has better performance in terms of leading to a solution, and whether the increased reasoning does not slow down system performance. 5.5 Testing the MahJong systems The Mah Jong system can run in two modes: with a ran­ domly generated layout, which has no guaranteed solution, Ol' with a solvable layout. Each layout is uniquely identified by a seed, which enables the use of the same layout for benchmarking. The systems will be tested on the following aspects by running them through a series of solvable games: • Average and spread of time for establishing a move. This measure is used to assess the performance and stability of the decision-making. • Average time to resolve a given layout. This measure is used to assess the overall performance of the system. • What kind of problems cause premature termination? This measure is used to find game-playing weaknesses in the system. • Frequeney of problems that cause premature termination. This measure is used to determine the robustness of the system. • Stability of the system, in particular in stepwise versus continuous running mode. This measure is used to de· termine the performance of the underlying multi-agent system architecture. 32 5.6 From MahJong to graphic unit recognition From the Mah Jong systems, we learo how to coordínate decision-making between agents. AJso, we learn how the prin­ ciples of communication by broadcasting in the multi-agent system apply. Thirdly, we can see how combined search- and recognition techniques for heuristics function in a dynamic setting. Finally, we gain some insight into the effects of dy­ namically rank ordering heuristics as a simple optimization mechanism. There are rwo main features that are lacking with respect to a system that can recognize graphic units: (l) there is no sophisticated learning mechanism; and (2) there is no user in the loop. AJthough the systems can optímise their internal rank ordering of heuristics, they are not capable of establish­ ing new heuristics or modifying existing heuristics. This may become an ímportant issue when the system needs to tune in on the architecťsdrawing style. The user in the loop can in­ crease the complexity of the environment of the multi-agent system, e.g., by erasing previously drawn objects, changing his mind about what he is drawing, startíng a new drawing, and so forth. These issues need to be resolved in further development. 6 Conclusions In the paper we have outlined the principal reasons why mul ti-agent systems can be used for the recognition of graphic units in drawings. To investigme the dynamics of a mul ti-agent system, we first implement a multi-agent system that can play Mah Jong. A framework for such a system has been established, and a Leve! O game-play system has been implemented. Heuristics for higher level game-play systems are described and a simple optimisation mechanism for es­ tablishing interna I rank ordering. The basics ofthis work will be used to implemem a mul ti-agent system that can recognize graphic units while the designer is drawing. Howevel~ three aspects stili need developmem: algorithms for graphic unit­ -description, learning mechanisms for the architecťs style, and coping with the user in the loop. 7 Acknowledgements The presented work was carried out by the principal author during a half-year sabbatical leave undertaken at the Faculty of Architecture of the Czech Technical University of Prague. The sabbatical leave was kindly hosted by Doc. Ing. Václav Kučera CSc., head of the Computer Aided Design group. The authors wish to thank both the Czech Technical University in Prague and Technische Universiteit Eindhoven in Eindhoven for supporting the research work. References [I] Achten, H.: Genem Representations - An Aptrroach for Modelling Procedural and Declarative Knowledge ofBuilding Types in Architectural Design. Eindhoven, Eindhoven Uni­ versit), ofTechnology, 1997. [2] Kavakli, M., Scrivener, S., Ball, L.: Structure in Idea Sketching Belulvior. Design Studies, Vol. 19, 1998, No. 4, p.485-517. Acta Polytechnica Vol. 43 No. 212009 t3l McFadzean, J.: Conputational Skehh Arnl^tser (CSA. In: "Proceedings of the lZth Conference on Education in Computer Aided fuchitecrural Design in Europe,' (Editors A. Brown and M. Ituight and p. Berridge;, iiv_ erpool: The University of Liverpool, 1999, p. SOS_StO. Pellitteri, G.: A Tool for a First Analysu of Archilecnral Fa- cadzs. Autornation in Constn_rction Vol. 5, lg97, No. 5, p. 379-391. Park, S., Gero,J.: Categorbation of Shapu Using Sh.ape Fea- tures. ln: "Artificial Intelligence in Design '00" (Editor J. Gero), Dordrecht: Kluwer Academic publishers. 2000. p.203-223. Gross, M.: The Electronb Cochtail Napkin -A Cornputational E-nuironment fcr Worhing With Design Dbgrams. Design Studies, Vol. 17, 1996, No. l, p. 53-69. McCall, R., Johnson, E., Smith, M: Hypersketching: De- sxgn. as Creating a Graphical Hyperdocumenl. In "CAAD futures 1997: Proceedings of the 7th International Con- ference on Computer Aided Architectural Design Fu- tures" (Editor R. Junge), Dordrecht: Kluwer Academic Publishers, 1997, p. 849-854. Qian, D., Gross, M.: Coll.o.borat,iue Design with Netdraw. In "Proceedings of the CAAD futures '99 Conference" (Editors G. Augenbroe and C. Eastman), Dordrecht: Kluwer Academic Publishers, 1999, p. 2lg-226. [l4] Nilsson, N.: Artif,cial Intelligmce: A New Synthes,is. San Francisco: Morgan Kaufmann publishers Inc., lg9g. [5] Weiss, G.: Multiagent Slstems - A Modzrn Approach to Dis- ttibuted Artificinl Intelligence. Cambridge: The MIT press, 2001. [6] Miiller, l. P.: Archileaures and, A@licatiorls of Intelligmt Agents: A Suwey. The Knowledge Engineering Review. Vol. 13, 1998, No.4, p.353-380. [7] Wooldridge, M., Jennings, N.: Intelligmt Agmts: The_ ory and Practire. The Knowledge Engineering Review. Vol. 10, 1995, No.2, p. lt5-152. [8] Wooldridge, M.: Intelligent Agents. In "Multiagenr Sys- tems - A Modern Approach to Distributed Artificial In_ telligence", (Editor G. Weiss), Cambridge: The MIT Press,200l, p.27-77. [l9] Luck, M: From Defnition to Deptolmmt: Whnt Next for Agent-Based Systerrc? The Knowledge Engineering Re- view. Vol. 14, 1999, No.2, p. ll9-124. [20] Minsky, M.: The Society of Mind. New york: Simon & Schuster, 1988. [2ll Maes, P.: The Dym,mits of Action Selection. In,,proceed- ings of the Eleventh International Joint Conference on Artificial Inrelligence ICAI-89", (Editor N. S. Sridahran), Detroit: Morgan Kaufmann, 1989, p. ggl-gg?. [22] Brooks, R: Elephnnts Don't Plny Cfuss. Robotics and Au- tonomous Sysrems. Vol. 6, 1990, p. 3-lb. [2 3] Franklin, S. : Artificinl Minds. Cambridse : The MIT press, 1995. t4l t5l t6l t7l t8l tgl Leclercq, P.: Programrning and Assisted Sketching - Graphic and Parametric Integration in Arclitectural Design. ln "Compurer Aided Architecrural Design Futures 2001" (Editors B. de Vries andJ. van Leeuwen and H. Achten), Dordrecht: Kluwer Academic publishers, 2001, p. l5-31. I l0] Do, E. et al: In,tentions in and. Relations Atnong Design Draw- ings. Design Studies. Vol.2l, 2000, No.5, p. a83-503. I l] Koutamanis, A.: Prolegontma to tlrc Recogttition oJ' Floor Plan Sketches. In "Design Research in the Nether- lands 2000", (Editors H. Achten and B. de Vries and J. Hennessey), Eindhoven: Eindhoven University of Technology, 2001, p. 95-105. [2] Rodgers, P., Green, G. McGown, A: Llsing Concept Shetches to Trach Duign Progress. Design Studies. Vol. 21, 2000, No. 5, p. 451464. [3] Russel, S., Norvig, P.: Artifcirzl Intelligence: A Mofum Ap- proach. Upper Saddle River: Prentice-Hall Inc., 1995. Associate professor Dr. Ir. Henri Hubertus Achten phone: +31 40 2472470 fax: *31 402450328 e-mail: h.h.achten@tue.nl Design Systems Group Vertigo VRT 9+H05 Design Systems Group Faculty of Architecture, Building and planning Technische Universiteit Eindhoven PO Box 512 5600 MB Eindhoven, The Netherlands 33 Scan28 Scan29 Scan30 Scan31 Scan32 Scan33