1. INTRODUCTION
As design takes place in an ever-changing environment, recent frameworks for design focus on dynamic character of its context (Campbell et al., Reference Campbell, Cagan and Kotovsky1999; Gero & Kannengiesser, Reference Gero and Kannengiesser2003; Sosa & Gero, Reference Sosa, Gero and Gero2004). This paper proposes a novel computational framework for computer-aided adaptive design. It uses the concept of grammar-based intelligent agents, which control the dynamic multifunctional design process and support the designer in a conceptual phase of this process. The organization, design methodology, and a semantic model of a grammar-based multiagent design system are presented.
Our system of agents is treated as a concurrent modular self-controlling open system that is able to solve complex design tasks. The architecture of the proposed design system is based on a collection of intelligent grammar-based agents that communicate with each other and autonomously control the development of subtask solutions. The design context is expressed by the environment in which agents act and predicates describing design criteria.
The behavior of our design agent is modeled by a set of grammar rules. Each agent has a hypergraph grammar and a database of facts concerning the subtask for which it is responsible. The novelty of our approach lies in the fact that the agents create their own design representations in the form of hypergraphs using rules of hypergraph grammars. Because of the representation that was used, the agents are capable of adapting to changes in the design problem specification and realizing adaptive search for solutions. The design knowledge encoded in hypergraphs enables agents to behave dynamically, as they are able to evaluate not only complete solutions but also partial solutions representing current states of objects being designed, and on this basis make subsequent design decisions. Agents plan their future behavior by choosing grammar productions that are to be applied.
This paper presents our attempt to develop a grammar-based multiagent system that supports the designer in the earliest stages of architectural design. Section 2 describes related work. In Section 3 the architecture of a proposed design system and the information flow in it are presented. The way in which grammar-based agents work is also explained. In the next section formal notions of an agent, a multiagent system, and agent knowledge are invoked. Section 4 describes internal representations of designs in the form of hierarchical hypergraphs and hypergraph grammars used by design agents to derive these hypergraphs. Elements of the language generated by cooperating agents are then interpreted as design solutions. Section 5 presents a semantic model of a grammar-based multiagent design system. The notions of valid designs and consistent design solutions are also discussed. In Section 6, the proposed approach is illustrated by the example of designing a house estate with the assistance of several cooperating grammar-based agents. The manager agent generates the arrangement of the whole estate compatible with the given specification and invokes agents designing the garden and the house interior. The agent that is responsible for designing furnished floor layouts has agent assistants generating furniture arrangements for different types of spaces in the house. The implementation section gives an outline of our prototype design system. Finally, some conclusions are drawn.
2. RELATED WORK
Recently, a great deal of design research has been focussed on developing agent-based design systems (Myers & Pohl, Reference Myers and Pohl1994; Lander, Reference Lander1997). The computational models and implementations of agents and collections of agents based on psychological models of social cognitive abilities are described (Velasquez & Maes, Reference Velasquez and Maes1997; Kokoszka et al., Reference Kokoszka, Bielecki and Holas2001). Models of motivated, emotional agents (Canamero, Reference Canamero1997) and curious agents (Saunders, Reference Saunders2001; Grabska et al., Reference Grabska, Ślusarczyk and Grześ2005) are also presented. Sapient agents, which learn to refine the decision-making capability and are able to make long-term strategic decisions, are described in Dzeroski (Reference Dzeroski2002). Adaptive, agent-based methods of conceptual design are presented in Campbell et al. (Reference Campbell, Cagan, Kotovsky, Gero and Sudweeks1998), whereas design systems with learning agents that form some expectations are described in Grecu and Brown (Reference Grecu, Brown and Gero2000). Many of these approaches establish an efficient communication between agents to handle design subtask, but they are not flexible enough to deal with the dynamic nature of design that is particularly important in conceptual stages of design.
In contrast, shape, structural, and graph grammars are widely used in architectural and engineering design (Stiny & Mitchel, Reference Stiny and Mitchell1980; Longenecker & Fitzhorn, Reference Longenecker and Fitzhorn1991; Carlson et al., Reference Carlson, Woodbury and McKelvey1993; Borkowski & Grabska, Reference Borkowski and Grabska1995; Cagdas, Reference Cagdas1996; Cagan, Reference Cagan, Antonsson and Cagan2001; Soman & Campbell, Reference Soman and Campbell2002). Most of these approaches use other tools to deal with semantics of design. For example, rules of a shape grammar generating coffeemakers are linked with expressions determining the manufacturing costs of designs in Agarwal et al. (Reference Agarwal, Cagan and Constantine1999).
Lately, different types of grammars are combined with agent-based systems. Some grammatical models of multiagent systems modeling eco systems can be found in Paun and Salomaa (Reference Paun and Salomaa1999). In McCormack and Cagan (Reference McCormack and Cagan2002), each shape grammar rule used in hood panel design is associated with one instantiation agent that controls the application of this rule. However, these approaches do not provide internal representations of designs that would uniformly encode syntactic and semantic design knowledge, and would be appropriate for automatic processing. Therefore, we propose a computational framework, where grammar-based agents operate on hierarchical design representations ground in the hypergraph theory (Habel & Kreowski, Reference Habel and Kreowski1987; Drewes et al., Reference Drewes, Hoffmann and Plump2000). The evaluation method based on hierarchical hypergraphs corresponding to partial solutions is more meaningful than the one presented in our previous work (Grabska et al., Reference Grabska, Grzesiak-Kopeć, Ślusarczyk and Alexandrov2006b), where agents evaluate designs using a neural network. Moreover, it allows agents to manipulate design representations in a dynamical way and adapt to changes in design. This approach is modeled in a similar way as a situated function–behavior–structure design framework described in Gero and Kannengiesser (Reference Gero, Kannengiesser and Gero2002).
3. A SYSTEM OF INTERFACE DESIGN AGENTS
The proposed multiagent design system consists of the context, which contains the environment and the specified design criteria, the message buffer, and a few kinds of agents acting simultaneously and performing different tasks. In the presented approach interface agents being designer's assistants are used.
The application of intelligent agents in the process of design is illustrated by the example of designing a house estate. The main goal of this task is to provide a well-organized, furnished living space inside a house and a suitably arranged garden.
The distinguished manager agent is responsible for designing the arrangement of the whole estate. The manager agent delegates tasks to the garden designing agent and the house interior designing agent. The latter one is responsible for designing the floor layout. It has agent assistants generating furniture arrangements for different types of spaces in the house. Eventually, the manager agent combines designs generated by itself, the “garden agent” and the “house interior” agent, and sends them to the environment. The environment, which is also treated as an agent, evaluates the obtained solutions and stores them in the global database. It keeps the best designs and a few poorer ones that can lead to long-term benefits. The design solutions put into the database by the environment can be visualized as the graphical models using a given interpretation.
The information flow in the system is shown in Figure 1. A dashed line, which crosses arrows linking agents, denotes the fact that agents and the environment communicate with each other through the message buffer.
Fig. 1 Information flow in the proposed system.
The proposed system is suitable for such a design task, as each agent can independently realize adaptive search for solutions of a subtask for which it is responsible. The agents are equipped with programmed hierarchical hypergraph grammars generating attributed hypergraph representations of design solutions and task-oriented databases that together represent their local knowledge. Grammar rules encode the structural aspects of possible solutions, whereas values of hypergraph attributes correspond to design constraints. The flow of information related to the internal processes of a single design agent that communicates with other agents through the message buffer is presented in Figure 2. The names in brackets denote agent's processes that are specified in Definition 4.1.
Fig. 2 The way in which a grammar-based design agent works.
First, the agent senses the message buffer and reads the obtained message. Then the type of the message, which is in the form of an attributed hypergraph, where values of attributes carry over the design requirements, is recognized in the perception process. When a hypergraph corresponding to a subtask solution generated by the other agent is received in the message, the adequate modification of the generated hypergraph is made.
When the message requires solving a subtask, the attributes of a hypergraph representing an internal state of the agent are updated according to the ones included in the obtained message. Then the derivation of a new hypergraph design representation is started. It should be noted that the agent can be invoked by other agents each time with different values of attributes. In this way the design requirements encoded in hypergraph attributes enable agents to adapt to changing design problem specifications.
After each modification of the generated hypergraph the evaluation of the current solution takes place and a decision about the next action is made. Either a message (a generated solution, a request of cooperation or notification of an error) is sent to the buffer or an internal action is taken. As a result of an internal action a successive rewriting step on the derived hypergraph is performed using a selected grammar rule, or a complete solution is stored and the generation of a new one is started. Thus, because of the evaluation of partial solutions representing current states of design, agents make decisions concerning grammar productions that should be applied, and in this way select the direction of search for valid solutions.
4. KNOWLEDGE REPRESENTATION IN A MULTIAGENT DESIGN SYSTEM
A design agent is a computational entity situated in some environment and capable of acting autonomously in this environment to satisfy requirements of the assigned design task. Its behavior is determined by processes of sensing, perception, evaluation of solutions, decision making, performing internal actions, and affecting the environment by external actions. The effectoric capability of an agent is assumed to be represented by the set of its actions (Wooldridge, Reference Wooldridge and Weiss1999). Each intelligent agent should possess two types of memory: a short-term memory and a long-term one. The short-term memory allows the agent to remember a few recent perceptual and conceptual states. The long-term memory stores agent's generalized experiences from the past.
Let us define an intelligent agentin a formal way. Let W denote a set of possible states of the world. Let S = {s 0, s Reference Agarwal, Cagan and Constantine1, …}, P = {p 0, p Reference Agarwal, Cagan and Constantine1, …} and C = {c 0, c Reference Agarwal, Cagan and Constantine1…} denote sets of sensor, perceptual, and conceptual states, respectively.
Definition 4.1
An intelligent agent with a short-term (M S) and long-term memory (M L) is defined as a tuple Ag = (Int, A, σ, ρ, η, χ, α), where Int = {int0, intReference Agarwal, Cagan and Constantine1, …} is a set of agent's internal states, A = {a 0, a Reference Agarwal, Cagan and Constantine1, …} is a set of its actions, σ: W → S is the world sensing process, ρ: S → P is the perception process being the interpretation of data obtained from sensors, η: Int × P → Int is the internal state changing process, χ: Int → C is the evaluation and decision-making process during which an internal state is evaluated and new goals are specified, and α: C → A is the action process that translates goals specified by a conceptual state to an action that should be taken. ▪
In our approach, the world W = {w 0, w 1, …} of design agents is a set of hypergraphs representing solutions and generated by all agents in a parallel way. A set of agent's internal states Int includes hypergraphs being derived using productions of its grammar. Perceptual states correspond to requirements obtained in messages, whereas conceptual states represent hypergraph evaluation results, which are then stored in variables of the short-term memory. The long-term memory is in the form of a database of the created admissible solutions. The agents' actions are depicted in Figure 2.
A multiagent design system is composed of a collection of agents Ag1, … , Ag n and the environment that they occupy. The definition of a multiagent system is preceded by the one of an environment that follows (Fagin et al., Reference Fagin, Halpern, Moses and Vardi1995; Wooldridge & Lomuscio, Reference Wooldridge and Lomuscio2000).
Definition 4.2
An environment is a tuple: Env = (W, A E, K 1, … , K n, τ), where W = {w 0, w 1, …} is a set of possible states of the world; A E = {a E0, a E1, …} is a set of environment actions; K i: W → W Agi ∈ 2W is a partition of W for every agent Agi, which characterizes information available to an agent in every environment state; and τ: A E × A 1 × ⋯ × A n → 2W is a state transformer function, which maps an action of the environment being in a given state and one action of each agent to the set of environment states that can result from the performance of these actions in this state.▪
Definition 4.3
A multiagent system (Wooldridge & Lomuscio, Reference Wooldridge and Lomuscio2000) is a structure AS = (Env, Ag1, … , Agn), where Env is an environment specified as in Definition 4.2 and Ag1, … , Agn are intelligent agents determined as in Definition 4.1.▪
At any moment of time the system is in a global state. The set of global states GS of the system AS contains subsets of W × Int1 × · · · × Intn. The functioning of the system is realized by changes of the global states described by the environment state transformer function τ and the agents' internal state changing functions ηi.
The initial global state is of the form g 0 = (w 0, int10, … , intn0). At this point every agent Agi senses the environment computing s i0 = σi(K i(w 0)), on the basis of s i0 establishes its initial perception state p i0, updates its internal state, which becomes inti1 = ηi(inti0, p i0) and selects the first action, which should be performed as a i0 = αi(χi(inti1)). The state of the environment is updated as w 1 = τ(a E0, a 10, … , a n0), and the system reaches the next global state g 1 = (w 1, int11, … , intn1).
In our system the initial state w 0 has a form of one hyperedge from which the derivation starts. Its attributes specify the design requirements like the number of rooms in a house. Initial internal states of the agents int10, … , intn0 are empty hypergraphs. When an agent Agi senses that it is invoked by the environment or the other agent, it identifies the obtained message with the initial hyperedge of its grammar, which becomes its next internal state int1i.
A prepositional multimodal logic is often used to represent and reason about various aspects of multiagent systems (Gaborit et al., Reference Gaborit, Potet and Sayettat1990; Traverso & Spalazzi, Reference Traverso and Spalazzi1995; Wooldridge, Reference Wooldridge, Wooldridge and Jennings1995). To represent knowledge possessed by design agents we define an interpreted system I AS and then associate with it a Kripke structure (Fagin et al., Reference Fagin, Halpern, Moses and Vardi1995).
We assume that we have a set Φ of primitive propositions that describe basic facts about the system. A run of AS over GS is a function r: N → GS so it can be identified with any sequence of global states over GS. Let R denote a set of runs over GS.
Definition 4.4
An interpreted multiagent system I AS generated by the structure AS is a pair (GSAS, π), where GSAS = ∪r∈Rr(N) is a set of all global states reachable by AS and π is an interpretation for the propositions in Φ over GS, which assigns truth values to the primitive propositions at the global states.▪
There is a one-to-one correspondence between each partition on W, which defines the possible worlds indistinguishable to the agent Agi in the given state of W (see Definition 4.2), and an equivalence relation on W. Given a partition K i on W the corresponding equivalence relation 핂 i is defined by (w′, w″) ∈ 핂 i iff K i(w′) = K i(w″).
A system I AS corresponds to the Kripke structure M I AS = (GSAS, π, 핂 1, … , 핂 N), where 핂 i ⊆ GSAS × GSAS is the equivalence relation corresponding to the partition K i on W and extended on GSAS in such a way that for each two global states g′ = (w′, int′1, … , int′n) and g″ = (w″, int″1, … , int″n), (g′, g″) ∈ 핂 i if (w′, w″) ∈ 핂 i and int′j = int″j.
The knowledge of a design agent is determined by its database, grammar rules, and generated hypergraphs. Having a set Φ of propositions describing design criteria the agent can test the validity of a generated solution by comparing values of hypergraph attributes with a given requirement.
Let 핂 1, … , 핂 n denote modal operators and let L denote a language obtained by closing off Φ under negation, conjunction, and the modal operators 핂 1, … , 핂n.
Definition 4.5
Agent Agi knows the formula ϕ ∈ L in a global state g = (w, int1, … , intn) of AS exactly if (M I AS, g)|= ϕ (i.e., ϕ is satisfied in state g of a structure M I AS). In other words, (I AS, g)|= 핂iϕ ⇔ π(h)(ϕ) = true for all h such that (g, h) ∈ 핂 i. ▪
5. HYPERGRAPHS AND HYPERGRAPH GRAMMARS USED BY DESIGN AGENTS
As many designed objects have hierarchical structures there is a preference for a hierarchical approach to modeling design (Suh, Reference Suh1990; Rosenman & Gero, Reference Rosenman, Gero and Bentley1999). Therefore, in this paper the representation of design object structures used by design agents is in the form of hierarchical hypergraphs (Ślusarczyk, Reference Ślusarczyk2003; Grabska et al., Reference Grabska, Grzesiak-Kopeć, Lembas, Łachwa, Ślusarczyk and Wojciechowski2006a), which allows representing objects on different levels of detail. Hyperedges of these hypergraphs enable us to express multiargument relations between different parts and subparts of objects.
Hypergraphs used in a multiagent design system contain two types of labeled hyperedges. Hyperedges of the first type are nondirected and represent parts of objects, whereas hyperedges of the second type represent relations among them. They are directed unless they represent symmetrical relations. Hyperedges of the hypergraph are labeled by names of the corresponding components or relations.
To represent features of objects and relations between them, attributing of hyperedges is used. Attributes represent properties (like shape, size, position, color, material) of elements corresponding to hyperedges. Values of attributes obtained by the agent when it is invoked specify the design requirements that should be met by the solutions.
Hyperedges representing object components can contain nested hypergraphs. Hierarchical hyperedges (with nonempty contents) represent object components with different functions or some groups of components. Hierarchical hypergraphs can be then mapped into various graphical models of the objects according to attributes assigned to these hypergraphs.
Let [i] denote the interval {1, … , i} for i ≥ 0 (with [0] = Ø). Let Σ = ΣC ∪ ΣR, where ΣC ∩ ΣR = Ø, be a fixed alphabet of hyperedge labels. Let At be a set of hyperedge attributes.
Definition 5.1
An attributed hierarchical hypergraph over Σ is a system H = (E H, V H, s H, t H, lbH, attH, extH, chH), where
1. EH = E C ∪ E R, where E C ∩ E R = Ø, is a finite set of hyperedges, where elements of E C represent object components and elements of E R represent relations,
2. V H is a finite set of nodes,
3. s H: E H → V H* and t H: E H → V H* are two mappings assigning to hyperedges sequences of source and target nodes, respectively, in such a way that ∀e ∈ E Cs H(e) = t H(e),
4. lbH: E H → Σ is a hyperedge labeling function, such that ∀e ∈ E C lbH(e) ∈ ΣC and ∀e ∈ E R lbH(e) ∈ ΣR,
5. attH: E H → P(At) is a function assigning sets of attributes to hyperedges,
6. extH: [n] → V H is a mapping specifying a sequence of hypergraph external nodes,
7. chH: E C → P(A) is a child nesting function, where A = V H ∪ E H is called a set of hypergraph atoms, and the following conditions are satisfied:
• one atom cannot be nested in two different hyperedges,
• a hyperedge cannot be its own child,
• source and target nodes of a nested hyperedge e are nested in the same hyperedge as e.▪
Hypergraph nodes express potential connections between hyperedges. To each hyperedge a sequence of source and target nodes is assigned. A hyperedge is called nondirected if sequences of its source and target nodes are equal. Moreover, for each hypergraph a sequence of its external nodes is determined. The length of this sequence specifies the type of a hypergraph.
Example 5.1
A hierarchical hypergraph representing an arrangement of kitchen equipment and furniture shown in Figure 3b is presented in Figure 3a. It contains three hierarchical component hyperedges. The hierarchical hyperedge labeled Kitchen represents a given space where the pieces are to be located. The four external nodes of this hyperedge represent four walls of the kitchen. The hyperedge labeled Eating place contains a hierarchical hypergraph composed of a hyperedge representing a table that is connected by a relational hyperedge with a hierarchical hyperedge labeled Chairs representing a group of four chairs. All other component hyperedges represent single pieces of furniture or kitchen equipment. A hyperedge labeling function assigns one name of the set ΣC = {Chairs, Eating place, Kitchen, chair, cooker, counter, fridge, sideboard, sink, stool, dishwasher} to each component hyperedge.
Fig. 3 (a) A hierarchical hypergraph representing a kitchen layout and (b) its visualization. [A color version of this figure can be viewed online at www.journals.cambridge.org]
There are five hyperedges representing distance relations between pieces. These hyperedges are labeled near or far, which means that some pieces should be located close to each other or possibly far away from each other, respectively. For example, sideboards should be placed close together, whereas a fridge and a cooker should be far away from each other. It should be noted that if a relational hyperedge is incident to a node connected with a component hyperedge with no empty contents, then the relation represented by this hyperedge is inherited by all hyperedges nested in the hierarchical one (e.g., all furniture located in the eating place should be placed far away from the cooker).
Shapes, colors, and location of the furniture or equipment are specified by values of three attributes, shape, color, and location, assigned to all nonhierarchical component hyperedges. The location can take value 0, which denotes that there are no constrains as to the location of the piece (e.g., stools, chairs), 1—the element should be placed by a wall (e.g., cooker, fridge, sink), 2—it can be located by the window (e.g., counter, table), or 3—it has to be placed by a wall or by the window (e.g., sideboard). The attribute area is assigned to hierarchical hyperedges.▪
When structures of designs are described in terms of hierarchical hypergraphs, hierarchical hypergraph grammars can serve as efficient tools for generating these structures. Application of grammar rules chosen by design agents corresponds to successive design actions. In this way design agents dynamically control the design process driving it toward solutions compatible with the design criteria.
A hierarchical hypergraph grammar is composed of a set of hypergraph edges with terminal and nonterminal labels, a set of hypergraph nodes, a set of productions, and an axiom being an initial hypergraph. Each grammar production is of the form p = (l, r, ξ, sr), where l and r are attributed hierarchical hypergraphs with the same number of external nodes equipped with ordering relations, ξ is a predicate of applicability, and sr is a set of semantic rules that specify the way in which values of attributes assigned to hyperedges of l are transferred to the attributes assigned to hyperedges of r.
Let N and T denote sets of nonterminal and terminal labels, respectively. Let A = V ∪ E be a set of atoms of H, where H denotes a family of attributed hierarchical hypergraphs over N ∪ T. Let lbH be a hyperedge labeling function.
Definition 5.2
A hierarchical hypergraph grammar over N and T is a system G = (V, E, P, X), where
1. V is a finite set of nodes,
2. E = E N ∪ E T is a finite set of hyperedges, with a child nesting partial function ch: E → P(A), where lbH: E N → N assigns nonterminal labels to hyperedges of E N, whereas lbH: E T → T assigns terminal labels to hyperedges of E T,
3. P is a finite set of productions of the form p = (l, r, ξ, sr) satisfying the following conditions:
• l and r are attributed hierarchical hypergraphs of the same type composed of nodes of V and hyperedges of E N∪ E T,
• l contains at least one hyperedge of E N,
• ξ: H → {TRUE, FALSE} is a predicate of applicability,
• sr is a set of semantic rules defining values of attributes assigned to hyperedges of r.
4. X is a hyperedge of E N with its source and target nodes and such that ch(X) = Ø and called an axiom of G.▪
Our design agents use context-free hierarchical hypergraph grammars.
Definition 5.3
A context-free hierarchical hypergraph grammar is a system G = (V, E, P, X), where P is a finite set of productions of the form p = (l, r, ξ, sr) and such that l contains only one hyperedge of E N.▪
Example 5.2
Some productions of a context-free hierarchical hypergraph grammar generating structures describing kitchen layouts are presented in Figure 4 (the predicates of applicability and semantic rules are omitted for the sake of simplicity; they can be found in grammar rules shown later). The first two productions enable the agent to create a kitchen layout with or without the eating place. The third and fourth productions enable the agent to locate a sink and a dishwasher near it or only a sink, respectively. The next two productions allow to fix a required number of sideboards, which should be placed close to each other. The productions p7 and p8 allow to add a counter and a stool, respectively. The last two productions enable the agent to locate a table and some chairs in the eating place.▪
Fig. 4 A context-free hierarchical hypergraph grammar generating structures of kitchen layouts.
The production p can be applied to a hierarchical hypergraph H if its predicate of applicability is satisfied. The application of p consists in substituting r for a hypergraph isomorphic with l, replacing external nodes of the hypergraph being removed isomorphic with nodes of extl by the corresponding external nodes of extr and determining values of attributes of r according to semantic rules of sr.
Definition 5.4
Let G = (V, E, P, X) be a context-free hierarchical hypergraph grammar and h′, h″ be two attributed hypergraphs, where h″ is said to be directly derivable from h′ (h′ ⇒ h″) if there exists a production p = (l, r, ξ, sr) of G such that ξ is satisfied for h′, h is a subgraph of h′ isomorphic with l, and h″ is isomorphic with the result of replacing h in h′ by r, substituting external nodes of h by the corresponding external nodes of r and assigning values to attributes of r according to sr.▪
The language generated by a given context-free hierarchical hypergraph grammar is a set of hypergraphs generated starting from the grammar axiom and such that all their hyperedges have terminal labels.
Definition 5.5
Let G = (V, E, P, X) be a context-free hierarchical hypergraph grammar. The language generated by G is a set L(G) = {h ∈ H|X ⇒* h and ∀e ∈ E hlbh(e) ∈ T}.▪
A hierarchical hypergraph grammar of each agent is equipped with a control diagram. A control diagram, which determines the order in which grammar productions can be applied, is a directed graph whose nodes are labeled by names of productions. Moreover, there are two distinguished nodes, the initial one with no edges coming into it and the final one with no edges coming out of it, labeled by I and F, respectively. If a subgraph isomorphic with the left-hand side of a production that should be used is not found in a generated hypergraph, the production will not be applied.
Definition 5.6
A programmed hierarchical hypergraph grammar is a pair G P = (G, CD), where G is a hierarchical hypergraph grammar and CD is a control diagram for G. ▪
Example 5.3
A control diagram for a hierarchical hypergraph grammar generating structures of kitchen layouts is presented in Figure 5. Each path from the node labeled I to the node labeled F represents one possible way of obtaining a hypergraph representing a potential arrangement. Application of a production sequence p2, p3, p6, p7, p8, p9, 4 × p10 results in the hypergraph shown in Figure 3a.▪
Fig. 5 A control diagram for a hypergraph grammar generating structures of kitchen layouts.
It should be noted that although a control diagram for a hypergraph grammar determines the order in which the productions should be applied, it still leaves the possibility of producing a variety of design alternatives as a great or even infinite number of paths leading to different solutions can be specified.
We are interested in a language that is generated by the cooperating agents that not only simultaneously develop different parts of a derived hypergraph but also delegate the derivation of some parts to other agents. Let G P1, … , G Pn denote context-free programmed hierarchical hypergraph grammars of design agents. The generation of a hypergraph representing a solution starts from the axiom X 1 of the manager agent's grammar G P1 and in the first step one of its productions is used. Then it can invoke other agents and the derivation process can take place in parallel. When an agent Agi obtains a message in the form of a hyperedge h it identifies h with the axiom X i of its grammar and starts the local derivation process. In each step an agent Agi either performs a rewriting step on a locally derived hypergraph using one of the productions of a grammar G Pi or replace a hyperedge in this hypergraph by a hierarchical hypergraph generated by the earlier invoked agent.
Let H denote a family of attributed hierarchical hypergraphs over N ∪ T.
Definition 5.7
Let h, h′, h″, g ∈ H. A derivation process in a multiagent design system with agents equipped with programmed context-free hierarchical hypergraph grammars G P1, … , G Pn is composed of direct derivations of the two following forms:
1. h″ is directly derivable from h′ (h′ ⇒ 1h″) using one of the productions of G Pi, 1 ≤ i ≤ n, as specified in Definition 5.4.
2. h″ is directly derivable from h′ (h′ ⇒2h″) if there exists a hyperedge h in h′(isomorphic with axiom X i of G Pi, 1 ≤ I ≤ n, g is an attributed hierarchical hypergraph generated starting from X i, and h″ is isomorphic with the result of replacing h in h′ by g and substituting external nodes of h by the corresponding external nodes of g.▪
The language generated by a multiagent design system is a set of hypergraphs, where all hyperedges have terminal labels, and generated by different agents starting from the axiom X 1 of the grammar G P1 of the manager design agent.
Definition 5.8
Let DAS be a multiagent design system with context-free programmed hierarchical hypergraph grammars G P1, … , G Pn.
The language generated by DAS is a set L(DAS) = {h ∈ H|X 1⇒1h 1{⇒1, ⇒2}* h and ∀e ∈ E h lbh(e) ∈ T}.▪
6. A SEMANTIC MODEL OF A GRAMMAR-BASED MULTIAGENT DESIGN SYSTEM
Each agent Ag of the design system has a context-free programmed hierarchical hypergraph grammar G P generating hypergraph representations of design solutions and a database B of facts concerning the subtask for which it is responsible. For example, an agent that designs a house interior has a set of architectural norms, like the minimal surface of rooms and their best geographical location, in its database.
Let a pair LK = (G P, B) represent a local knowledge of an agent.
Definition 6.1
A grammar-based design agent DA = (Ag, LK) is defined as an intelligent agent Ag = (Int, A, σ, ρ, η, χ, α) equipped with a domain-dependent local knowledge LK = (G P, B).▪
A design process takes place in a specified context that changes with time. This context is expressed by the environment in which agents act and predicates describing design criteria. In addition, agents inform and provide a context for one another. When the agent requires a cooperation it invokes other agents with the design requirements encoded in message attributes. Their values each time can be different according to new predicates.
Let GS denote a set of multiagent design system global states.
Definition 6.2
A context of a multiagent design system is defined as a tuple γ = (Env, g 0, ψ), where Env is the system environment, g 0 ∈ GS is the initial global state, and ψ is a set of predicates describing design criteria (functional requirements and constraints).▪
A collection of grammar-based design agents, a specified context and a communication buffer together constitute a grammar-based multiagent design system.
Definition 6.3
A grammar-based multiagent design system is a tuple DAS = (γ, M B, DA1, … , DAn), where γ is a context of a multiagent design system, M B is a message buffer used by agents and the environment, and DA1, … , DAn are grammar-based design agents.▪
As mentioned, the world W of design agents is as a set of hypergraphs that are generated by all agents in a parallel way. The multiagent design system works in the following way. Being in the initial global state the environment sends the message send(h 0, 1, 0), where 0 and 1 denote the environment and the manager agent, respectively, and h 0 is the hyperedge with well-specified values of all its attributes. At the next step the manager agent starts the hypergraph derivation process by identifying h 0 with the axiom of its grammar. In the successive steps it applies appropriate grammar rules or delegates further derivation to other agents by sending messages.
A set of each design agent's internal states Int is a set of hypergraphs derived using productions of its hierarchical hypergraph grammar. Each internal state intk corresponds to a hypergraph generated after k steps of derivation. The set of an agent actions A = A I ∪ A E contains internal actions A I and actions in the form ai = send(μ, j, n) ∈ A E, where μ denotes a message of a set M of messages, j is the identifier of the agent to which the message is sent, and n is the identifier of an agent that sends the message. The set M contains three types of messages: an error message, a generated hypergraph, which is returned to the agent that earlier requested cooperation, and a hyperedge with specified values of all attributes, which corresponds to delegating a design subtask to the other agent. Each internal action a i ∈ A I changes the current internal state of an agent by applying a hypergraph grammar rule to the hypergraph being derived, by replacing a hyperedge of the hypergraph with an obtained hypergraph, or by storing a complete solution and starting generation of a new one. In addition, A contains a special null action that corresponds to the agent performing no action.
In the sensing process a design agent searches the buffer for messages addressed to it. Thus, if the agent DAj performed an action send(μ, i, j), then the agent DAi in the k step of its run obtains the message as the result of sensing process σ. Then the kind of the obtained message μ is determined in the perception process ρ. In the next step, in the internal state changing process the values of design variables are updated according to the kind of the obtained message. μ is always in the form of an attributed hypergraph. If this hypergraph is empty, the message means that the agent DAj was unable to perform a delegated subtask. Therefore, the hyperedge in the hypergraph generated by the agent DAi that was to be further developed by the agent DAj remains unchanged. If μ has the form of a hypergraph containing more elements than one nonhierarchical hyperedge, it means that the agent DAj has returned a hypergraph corresponding to a subtask solution. In this case the appropriate hyperedge in the hypergraph generated by the agent DAi is replaced by μ. If μ in the form of such a hypergraph is obtained by the environment, then it represents a complete solution of a given design task, and is added to the global database of solutions. If μ has the form of one hyperedge, it means that the agent DAj delegated a subtask to the agent DAi. Then the values of design variables in the short-term memory are updated according to the values of attributes of μ, μ is identified with the axiom of the agent's grammar G Pi and the generation of a new hypergraph is started.
Before each step of a hypergraph derivation an agent evaluates its current internal state representing a partial solution and selects an action in a decision making process χ. As a result of the next grammar rule application, the internal state of the agent is changed. When no further rule can be applied and the derived hypergraph h does not belong to the language generated by the agent (h ∉ L(G Pi)), a message in the form of an empty hypergraph is sent to the agent DAj by which the considered one was invoked. If h ∈ L(G Pi), the message μ = h is sent to the agent DAj. If the cooperation of the other agent is needed, a message in the form a hyperedge, which should be further developed by the agent DAj, is sent to the message buffer.
The agent's evaluation capability depends on the possessed knowledge. This evaluation is based on the design knowledge included in the database of facts concerning the subtask it is responsible for and values of hypergraph attributes describing requirements and constraints specified in the design context. The agent evaluates both partial and complete solutions. The results of partial solutions evaluation influence the agent decisions about required modifications and the direction of further search for solutions.
Each design agent DAi has in its database B i an interpretation I i for hierarchical hypergraphs of L(G Pi). The interpretation determines the possible ways of mapping an attributed hierarchical hypergraph into graphical models by specifying a semantic meaning of hypergraph elements. It assigns geometrical objects to hyperedges representing artifact components, and establishes a correspondence between relational hyperedges and relations between these objects. The interpretation enables the agents to appropriately arrange object components and create a visualization of the whole designed object.
Definition 6.4
Let H = (E H, V H, s H, t H, lbH, attH, extH, chH) be an attributed hierarchical hypergraph over Σ = ΣC ∪ Σ R.
An interpretation for H is a function I = (I C, I R), where
1. I C: E C × ΣC → O, where O is a finite set of geometric objects, assigns objects to labeled component hyperedges,
2. I R: E R × ΣR → R, where R is a finite set of relations between geometric objects, assigns relations to labeled relational hyperedges. This function enables to correctly assign transformations that should be applied to geometric objects represented by component hyperedges when a hierarchical hypergraph visualization is created.▪
Example 6.1
The interpretation for the hierarchical hypergraph shown in Figure 3a assigns icons representing appropriate pieces to all component hyperedges according to their labels. A set of icons representing a fridge, cooker, sink, stool, table, counter, sideboard, and a dishwasher (from left to right) is shown in Figure 6. Then the transformations being compositions of translations and rotations are assigned to component hyperedges in a way that enable location of the icons according to the relations specified by relational hyperedges and values of the component hyperedge attribute location described in Example 5.1. They ensure that the cooker, fridge, and sink are located by the wall, the cooker is placed far from the fridge, table, chairs, and so forth. Three graphical models corresponding to the considered hypergraph are shown later.▪
Fig. 6 Icons representing kitchen pieces. [A color version of this figure can be viewed online at www.journals.cambridge.org]
Let G P1, … , G Pn denote hierarchical hypergraph grammars of design agents DA1, … , DAn and I 1, … , I n denote agents' interpretations for elements of L(G P1), … , L(G Pn), respectively. For each hypergraph h of L(G Pi), I i(h) is called a graphical model of h.
The interpretation I for the DAS is defined as I = I 1 ∪ · · · ∪ I n. The global database DB of the system contains hypergraphs belonging to the language L(DAS) generated by a DAS with grammars G P1, … , G Pn. Thus, I(L(DAS)) denotes a set of all graphical models reachable by the grammar-based multiagent design system.
Definition 6.5
Let π be an interpretation for the predicates of ψ over I(L(DAS)). An interpreted design system I DAS generated by the structure DAS is a triple (DB, I, π).▪
Statement 6.1
Given an interpreted design system I DAS = (DB, I, π). A hypergraph h ∈ DB is a valid design solution in respect to ϕ ∈ ψ if the manager design agent DA M, which starts the generation of solutions and sends the generated ones to the environment, knows that the formula ϕ is satisfied for h. In other words, (I DAS, h)|= 핂 Mϕ ⇔ π(ϕ(I(g))) = true for all g isomorphic with h.▪
Statement 6.2
An interpreted design system I DAS generates design solutions consistent with the design criteria if ∀h ∈ DB∀ϕ ∈ ψ(I DAS, h)|= 핂 Mϕ.▪
The agents of a grammar-based multiagent design system jointly solve a problem by modifying the contents of a global database. Thus, computations are situated and connected to the context through interaction.
7. CREATIVE DESIGN WITH INTELLIGENT GRAMMAR-BASED AGENTS
At the beginning of the design process all the information needed to perform a design task is supplied by the designer who has to take into account all needs of the client. Input information includes a description of the estate, garden, garage, and rooms required in the house, as well as the style and types of furniture. The global database of generated solutions can be empty or include some prototypical solutions of similar tasks, whereas the communication buffer where messages from agents are stored is empty.
7.1. The estate manager design agent
The requirements and constraints of the design project are specified in the initial state of the environment as values of attributes of the initial hyperedge. The manager agent, which is responsible for the whole design task, is expected to generate the arrangements of the whole estate using rules of the given hypergraph grammar, combine it with furnished floor layouts and garden arrangements generated by other agents, and return task solutions to the environment.
At the outset of the design the environment sends a message to the manager agent in the form of an attributed hyperedge. The perception process of the manager agent consist of reading and storing attributes of this hyperedge describing the design requirements, like the number of rooms in the layout, their area and shape, the area and the features of the garden, the necessity of creating a garage. The internal state of the agent is changed by updating the values of design variables (stored in the initial state of agent's short-term memory) and identifying the obtained hyperedge with the axiom of the agent's grammar. Thus, the new internal state is obtained and the agent starts the hypergraph derivation process using grammar rules.
Example 7.1
Two selected productions of a hierarchical hypergraph grammar of the estate manager agent with predicates ξ determining the conditions of their applicability are presented in Figure 7b. Some semantic rules defining the way in which values of attributes of the right-hand sides are inherited from the ones of the left-hand sides are shown. The first production is applied if a garage should be present and the garden should be accessible from the north side of the house. The second production allows the agent to generate an estate without a garage and with the garden accessible from the east side of the house. The hyperedge labels House Interior and Garden indicate that the design of these parts will be delegated to other agents. ▪
Fig. 7 (a) A hyperedge with design requirements and (b) two rules of a hierarchical hypergraph grammar of the manager design agent.
On the basis of the current internal state the agent either chooses a local action or sends a message. A local action consists in applying a grammar rule that corresponds to the specified values of design variables.
Example 7.2
Let us assume that the manager agent obtains an initial hyperedge shown in Figure 7a with fixed values of hyperedge attributes, which reflect the requirements concerning the area of a house, garden, and garage, the number of bedrooms, and the garden location. Given this set of example constrains the agent searches for a feasible layout of the estate. The values of the attributes obtained from the environment make the agent apply the second production.▪
When the solution being generated does not satisfy the required conditions the agent sends an “error” message in the form of an empty hypergraph to the environment. If the agent finds in the generated hypergraph a hyperedge with a label House Interior or Garden, which indicates that the cooperation of another agent is needed, it sends a message in the form of this hyperedge with the current values of its attributes to the agent, which should generate an arrangement for the space corresponding to the found label. As the agent sensors scan the message buffer it can easily spot the solution returned by the earlier invoked agent. Then it takes the other local action and combines the returned arrangement with the solution generated by itself by replacing the earlier sent hyperedge with the obtained hypergraph.
7.2. The house interior design agent
The house interior design agent generates structures of floor layouts. It starts the generation of a hypergraph after obtaining a message in the form of a hyperedge labeled House Interior.
Example 7.3
Some rules of a hierarchical hypergraph grammar of an agent generating house interiors are shown in Figure 8. The attributes of component hyperedges of both sides of productions, some semantic rules, and predicates of applicability are depicted for the first three productions. All relational hyperedges represent accessibility between the rooms. The first production divides the floor area into three functional units, a hall, a kitchen, and an antechamber under the condition that there is more than 60 mReference Borkowski and Grabska2 to be used. The second and third production allow us to choose a layout with one or two bedrooms in the first sleeping area. The fourth production adds a living room connected with a terrace. The productions p5 and p6 enable the agent to obtain different layouts composed of two rooms, a shower, and a small hall. The former rule gives a possibility to locate the shower between the rooms, whereas the latter one allows the shower to be adjacent to the one room only, but to have two entrances, one from the hall1 and the second from the room. A control diagram for this hypergraph grammar is shown later.▪
Fig. 8 Some of the rules of a hypergraph grammar generating structures of floor layouts.
After each step of derivation the house interior design agent evaluates the partial solutions, which are possible to obtain by using admissible grammar rules in respect to the information in the database and requirements specified in the design context.
Example 7.4
Let us assume that the agent generating floor layouts obtained a hyperedge e labeled House Interior with house_area(e) = 150 mReference Borkowski and Grabska2, room_number(e) = 3. Then these values are given to the attributes of the grammar axiom, which is isomorphic with the left-hand side of the first production. After application of this production the value of the attribute room_number of the hyperedge labeled Sleeping1 is equal to 1 and therefore in the next step the second production is applied. A hypergraph generated by the grammar according to the mentioned criteria is shown in Figure 9, whereas one of the possible floor layouts corresponding to this hypergraph is shown in Figure 10a.
Fig. 9 A hypergraph generated by the hypergraph grammar from Figure 8.
Fig. 10 (a) A floor layout corresponding to the hypergraph from Figure 9 and (b) a floor layout with a kitchen arrangement. [A color version of this figure can be viewed online at www.journals.cambridge.org]
The considered grammar contains two productions: one generating two rooms and another generating three rooms in the Sleeping1 area, both applicable when the value of room_number attribute is greater than 1. In such a case, the agent selects a production to be applied on the basis of the current value of the attribute area of the hyperedge Sleeping1. If this value is smaller than 30 mReference Borkowski and Grabska2, the agent creates only two rooms using production p3. After application of this production the agent evaluates the obtained hypergraph using its database. It checks if the values of the attribute area of both hyperedges labeled room are in the range specified for a bedroom area in the database. If they are smaller than the stored norms an error message is sent to the manager agent. The hypergraph generated using productions p3 and p5, according to the design requirements including four bedrooms and a shower accessible from two sides, together with the corresponding floor layout are presented later.▪
At each step the agent applies the most promising grammar production selected from the set of rules that can be used at this point of derivation or sends a message to the other agent. If the generated hypergraph contains hyperedges labeled by elements of the set {living-room, room, bath-room, kitchen} the house interior design agent delegates tasks to the agents generating furniture arrangements for appropriate types of spaces in the house. Then it combines the returned arrangements with the solution generated by itself. The floor layout combined with a kitchen arrangement (a fridge, cooker, sink, dishwasher, counter, stool, two sideboards, and a table with four chairs) is shown in Figure 10b.
7.3. The furniture arrangement design agents
There are four agents generating furniture arrangements in the system. They produce layouts for livingrooms, bedrooms, bathrooms, and kitchens. Each of them is invoked by the house interior design agent when the appropriate hyperedge label occurs in the hypergraph generated by this agent.
The knowledge bases of these agents contain sets of icons (graphic representations) corresponding to the predefined furniture and equipment. The values of the attributes assigned to these icons specify the shape, color, and location of the furniture or equipment.
Example 7.5
Two-dimensional graphic representations of a furniture set in the knowledge base of an agent generating arrangements for living rooms are shown later. They correspond to a couch, armchair, table, bookcase, coffee table, television set, chair, wardrobe, and a cupboard.▪
When an arrangement agent senses the message in the communicating buffer it reads the attributes describing the design criteria (like the area of the space, the location of doors and windows) in the perception process. Then it starts generation of the arrangement using a given hypergraph grammar and a knowledge base where the information about furniture and equipment for the given space is stored.
As the behavior of all furniture arrangement agents is similar, it will be explained on the example of the kitchen arrangement agent. Its database of equipment contains information about a sink, dishwasher, cooker, fridge, sideboard, counter, stool, table, and chair. Analogously as the manager and the house interior design agents, the furniture arrangement agent after each step of derivation also evaluates the partial solutions possible to obtain in respect to the given requirements and makes the decision about the action that is to be taken next.
Example 7.6
The agent's hypergraph grammar generating structures describing kitchen layouts is presented in Figure 4. A production that generates a hypergraph with a hyperedge representing an eating place in the kitchen is used only when the value of the attribute area assigned to the hyperedge Kitchen (rule p2) is greater than 10 mReference Borkowski and Grabska2. In the opposite case, there would not be enough space for all needed equipment or the arrangement of furniture would not be comfortable.▪
Hypergraphs obtained in the derivation process and representing partially specified solutions can be mapped into graphical models using a given hypergraph interpretation (Grabska et al., Reference Grabska, Ślusarczyk and Papiernik2003). Thus, each furniture arrangement design agent has the following three types of rules: hypergraph grammar rules, which are used to generate hypergraphs representing pieces arrangements; interpretation rules, which enable the agent to map a generated hypergraph into a graphical model by assigning semantic information to hypergraph elements; and constrain rules, which describe the possible sizes and orientations of geometric primitives of a database by specifying admissible scaling and rotations.
Evaluation of partial solutions enables the agent to select the grammar rule, which should be used in the next derivation step, take decisions about required modifications or find some new design concepts and requirements. If some modifications of the generated solution are required, modifying rules, which can be added to the hypergraph grammar, may be used (Ślusarczyk, Reference Ślusarczyk2004). When new design ideas or requirements emerge the agent can create new grammar rules and add them to the control diagram (Grabska et al., Reference Grabska, Grzesiak-Kopeć, Ślusarczyk and Baker-Plummer2006c). The inspection of partial solutions at successive stages of the design process allows the agent to evaluate many possible variants of component arrangements and to choose the proper direction of search.
Each arrangement design agent generates a set of solutions that are compatible with the initial requirements. This set can be treated as the contents of the agent's long-term memory. Therefore, when the house interior design agent invokes an arrangement agent for the second time with the same initial requirements it can behave in a reactive manner returning one of the earlier generated solutions. However, in case of new initial requirements it has to start the generation again.
Example 7.7
Three different kitchen arrangements generated for the same the criteria specification (an eating place with a table and chairs, a dishwasher near a sink, a fridge far from the cooker, and at last two sideboards and one counter) are presented in Figure 11.▪
Fig. 11 Three different kitchen arrangements compatible with the same criteria. [A color version of this figure can be viewed online at www.journals.cambridge.org]
Grammar-based design agents can effectively assist the in the design process. They not only cooperate with each other but also dynamically react to changes in the design context.
Example 7.8
Three examples of the results obtained using five cooperating grammar-based agents to the problem of designing house interiors with furniture arrangements are shown in Figure 12. The rooms of the floor layout from Figure 10a are filled with different furniture arrangements. ▪
Fig. 12 Three different furniture arrangements for the same floor layout. [A color version of this figure can be viewed online at www.journals.cambridge.org]
8. IMPLEMENTATION OF THE SYSTEM
The prototype multiagent design system is written in Java, and enables us to verify the proposed approach. It contains one module for each agent type. In each module the designer can define the agent's hypergraph grammar and add to a database constrains concerning geometric primitives corresponding to component hyperedges. The interface window of the agent that generates floor layouts of a house is shown in Figure 13. In its upper part the designer defines a hypergraph grammar of the agent. One of the productions of this grammar is presented in the right-hand side panel. On the left-hand side of the upper part of the window the attributes and semantic rules of productions are specified. A control diagram for the hypergraph grammar can be defined and edited in the bottom left-hand side panel.
Fig. 13 An interface of a floor layout design agent. [A color version of this figure can be viewed online at www.journals.cambridge.org]
When the manager agent is activated and the system starts to work, the designer can switch between the windows of different agents. In the bottom right-hand side panel the hypergraph generated by a given agent, its graphical model, or both views together with the transparent hypergraph on the top of the layout can be seen. A hypergraph generated by a house interior design agent together with a layout being its graphical model is presented on the right-hand side of Figure 13. The labels of hyperedges are listed on the left of the hypergraph. The same panel with a furniture layout for a living room generated by one of the arrangement agents is shown in Figure 14a. Some icons representing furniture of this agent database are shown on the right-hand side of this panel.
Fig. 14 (a) A furniture layout of a living room and (b) a floor layout of a house with a furnished living room. [A color version of this figure can be viewed online at www.journals.cambridge.org]
The bottom right-hand side panel of the agent's window is also used to present hypergraphs obtained after replacing some hyperedges by hypergraphs generated by cooperating agents and their graphical interpretations. A panel with a floor layout of a house with a living room filled with furniture, which corresponds to the hypergraph generated by the house interior design agent, where the hyperedge labeled living_room was replaced by a hypergraph returned by the living room arrangement agent, is shown in Figure 14b. In the present version of the system a graphical layout is created by locating first one primitive representing a room and then successively fitting others one by one to the previously located ones. There is no constraints solver used but all eventual inconsistencies can be modified in a free-hand mode.
9. CONCLUSIONS
Cooperating grammar-based design agents seem to be promising assistants in the process of creative design. In this paper a grammar-based multiagent design system was presented. Solutions created by such a design system can be easily adapted to the clients' individual needs without the designer intervention. The proposed semantic model of a design system enables agents to check whether generated hypergraphs representing design solutions are consistent with the design criteria. The interpretation of hypergraphs generated by the system allows the designer to view and evaluate graphical models of solutions.
A multiagent system with a collection of communicating interface design agents can model diverse requirements and constrains characteristic for dynamic design context. Context drives the design process by the influence on the way in which the agent makes the decisions: which rule to apply, when and where to apply it, when to terminate the generation, and which design solution to select. Thus, design requirements drive the solution development at each step of the generation process. Interaction with other agents and the feedback from the environment make the successful design possible.
In this paper we focused on systems composed of agents with one type of grammars. In our future work we intend to extend this approach to incorporate agents equipped with nonvisual descriptive grammars and working on the global database of already created designs. Such agents could, for example, compute quantitative or qualitative information about designs generated by other agents. They could query the database to find the most plausible designs, estimate the costs of building and furnishing the designed houses, and arranging the planned gardens, evaluate the accessibility of needed materials and garden plants. They should also be able to search the database for already existing solutions to a problem similar to a given new one.
As an agent's decision method for choosing goals is based on current information about the design task, the agent should be capable of learning and abstracting knowledge. Therefore, we intend to equip design agents with a learning function. On the basis of the evaluation notes given by other agents, environment, or the designer to hypergraphs representing generated solutions the agent will learn which sequences of grammar productions are preferred and modify the control diagram by updating weights determining the probability of production application.
In the present version of the system the agents cooperate and inform each other about the impossibility of finding valid solutions, but they do not negotiate. In the future, we would like the agents to have more influence on the other agents' decisions. For example, the furniture arrangement agent should be able to make the floor layout design agent move some doors or windows.
Grażyna Ślusarczyk received her PhD degree from the Institute of Fundamental Technological Research PAS in 1999. She is a Lecturer in the Department of Design and Computer Graphics, Faculty of Physics, Astronomy, and Applied Computer Science, Jagiellonian University. Her research interests include graph transformations, computer-aided graphic design, and multiagent systems in design.
