New computational techniques for detecting, learning and managing criteria in design problems

New Computational Techniques for Detecting, Learning and Managing Criteria in Design Problems TESIS DOCTORAL Manuela Ruiz Montiel Universidad de Málaga Julio de 2016 AUTOR: Manuela Ruiz Montiel http://orcid.org/0000-0002-1824-7808 EDITA: Publicaciones y Divulgación Científica. Universidad de Málaga Esta obra está bajo una licencia de Creative Commons Reconocimiento-NoComercialSinObraDerivada 4.0 Internacional: http://creativecommons.org/licenses/by-nc-nd/4.0/legalcode Cualquier parte de esta obra se puede reproducir sin autorización pero con el reconocimiento y atribución de los autores. No se puede hacer uso comercial de la obra y no se puede alterar, transformar o hacer obras derivadas. Esta Tesis Doctoral está depositada en el Repositorio Institucional de la Universidad de Málaga (RIUMA): riuma.uma.es Documento maquetado con TEXiS v.1.0. New Computational Techniques for Detecting, Learning and Managing Criteria in Design Problems Memoria que presenta el doctorando Manuela Ruiz Montiel para optar al grado académico de Doctora Dirigida por el Doctor José Luis Pérez de la Cruz Molina Programa de Doctorado en Ingeniería del Software e Inteligencia Artificial Departamento de Lenguajes y Ciencias de la Computación Escuela Técnica Superior de Ingeniería Informática Universidad de Málaga Julio de 2016 Copyright ©Manuela Ruiz Montiel E-mail: [email protected] Web: http://www.lcc.uma.es/~mruiz This work is licensed under a Creative Commons Attribution-NonCommercialNoDerivs License: http://creativecommons.org/licenses/by-nc-nd/3.0/ El Dr. D. José Luis Pérez de la Cruz Molina, Catedrático de Universidad, del Área de Ciencias de la Computación e Inteligencia Artificial de la Escuela Técnica Superior de Ingeniería Informática de la Universidad de Málaga, Certifica que, Dña. Manuela Ruiz Montiel, Ingeniera en Informática, ha realizado en el Departamento de Lenguajes y Ciencias de la Computación de la Universidad de Málaga, bajo su dirección, el trabajo de investigación correspondiente a su Tesis Doctoral titulada: New Computational Techniques for Detecting, Learning and Managing Criteria in Design Problems Revisado el presente trabajo, estima que puede ser presentado al tribunal que ha de juzgarlo, y autoriza la presentación de esta Tesis Doctoral en la Universidad de Málaga. Fdo.: Dr. José Luis Pérez de la Cruz Molina Málaga, Julio de 2016 A Francis, Juanma y mamá List of Figures 2.1 A rule (a) and one derivation starting from an initial squared shape (b) 14 2.2 Seven rules of the Palladian grammar (reproduced from Stiny & Mitchell (1978))..................................... 17 2.3 The Villa Malcontenta as drawn by Palladio (reproduced from Stiny & Mitchell(1978))................................ 18 2.4 Q(0) algorithm (reproduced from Sutton & Barto (1998)) . . . . . . . . 25 2.5 Watkins’s Q(λ) algorithm (reproduced from Sutton & Barto (1998)) . . 27 2.6 A linear version of Watkins’s Q(λ) with binary features (reproduced from Sutton & Barto (1998)) . . . . . . . . . . . . . . . . . . . . . . . . 28 2.7 MOMDP problem taxonomy (reproduced from Roijers et al. (2013)) . . 30 3.1 Axes for classifying different approaches combining shape grammars and control..................................... 34 3.2 Location of a design system based on a pure expert shape grammar . . 35 3.3 Location of our system based on shape grammars, constraints, goals and layers ..................................... 37 3.4 A simple additive rule working with squared tiles . . . . . . . . . . . . . 37 3.5 Location of our system based on shape grammars and reinforcement learning .................................... 39 3.6 Location of our system based on naive shape grammars and random/- manualcontrol ................................ 40 3.7 Graphical interface of MG-Shade ....................... 41 3.8 A controlled mega-structure generated by a student . . . . . . . . . . . 41 3.9 A random mega-structure generated by a student . . . . . . . . . . . . . 42 4.1 Fragment of the derivation tree for the application of the rule in Figure 2.1....................................... 48 xv xvi List of Figures 4.2 Depth-first search of the tree of rule in Figure 2.1, with the specified predicates.................................... 49 4.3 A layered shape (n= 3) ........................... 51 4.4 A layered shape grammar . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.5 A shape α................................... 52 4.6 A shape γ................................... 52 4.7 ShaDearchitecture.............................. 54 4.8 ScreenshotofShaDe ............................. 56 4.9 GUI for predicate configuration: applied transformation . . . . . . . . . 58 4.10 GUI for predicate configuration: current shape labels . . . . . . . . . . . 58 4.11 Hele Module (reproduced from (Leoz, 1978)) . . . . . . . . . . . . . . . 59 4.12 Some Hele Module combinations (adapted from (Leoz, 1978)) . . . . . . 59 4.13 Set of predefined rooms . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.14 The axiom for the Leoz script . . . . . . . . . . . . . . . . . . . . . . . . 60 4.15 The layers of Leoz script for ShaDe . . . . . . . . . . . . . . . . . . . . . 61 4.16 Rule for Project 1 (Leoz example) . . . . . . . . . . . . . . . . . . . . . 62 4.17 Rule for Project 2 (Leoz example) . . . . . . . . . . . . . . . . . . . . . 63 4.18 Rules for Project 3 (Leoz example) . . . . . . . . . . . . . . . . . . . . . 63 4.19 Four designs produced by the Leoz design script . . . . . . . . . . . . . 64 4.20 A housing unit with height information and textures . . . . . . . . . . . 65 4.21 Screenshots of the games Restaurant Empire (a) and Restaurant Story (b)....................................... 66 4.22 The axiom for the restaurant script . . . . . . . . . . . . . . . . . . . . . 67 4.23 Rules for Project 1 (restaurant example) . . . . . . . . . . . . . . . . . . 67 4.24 Rules for Project 2 (restaurant example) . . . . . . . . . . . . . . . . . . 67 4.25 Rules for Project 3 (restaurant example) . . . . . . . . . . . . . . . . . . 67 4.26 Rule for Project 4 (restaurant example) . . . . . . . . . . . . . . . . . . 67 4.27 Rule for Project 5 (restaurant example) . . . . . . . . . . . . . . . . . . 68 4.28 Rule for Project 6 (restaurant example) . . . . . . . . . . . . . . . . . . 68 4.29 Four designs produced by the restaurant design script . . . . . . . . . . 69 4.30 A restaurant in three dimensions . . . . . . . . . . . . . . . . . . . . . . 70 4.31 A restaurant with textures (a) and with roof (b) . . . . . . . . . . . . . 70 4.32 Rule 4 of the third Leoz Project (flattened) . . . . . . . . . . . . . . . . 71 4.33 Performance measures: (a) number of triplets detected and (b) generation time in layered and unlayered approaches . . . . . . . . . . . . . . . 72 5.1 Possible solutions for the problem of generating 8-tile, compact shapes . 75 List of Figures xvii 5.2 Possible intermediate 2-tile shapes . . . . . . . . . . . . . . . . . . . . . 75 5.3 Possible intermediate 3-tile shapes . . . . . . . . . . . . . . . . . . . . . 76 5.4 Possible intermediate 5-tile shapes . . . . . . . . . . . . . . . . . . . . . 76 5.5 Train/test performance for the compactness problem . . . . . . . . . . . 83 5.6 Train/test performance for the compactness problem, for different discountrates .................................. 84 5.7 Shapewith8tiles .............................. 84 5.8 Pattern that represents two shapes obtained from the shape of Figure 5.7 sharing the same features . . . . . . . . . . . . . . . . . . . . . . . . 85 5.9 Shape represented by the best pattern obtained from the shape of Figure 5.7....................................... 85 5.10 Proximity relationships in a single-family house (adapted from Montaner Muxí arquitectes (2008)) . . . . . . . . . . . . . . . . . . . . . . . 88 5.11 Naive grammars for phases 1-6 . . . . . . . . . . . . . . . . . . . . . . . 90 5.12 Effect of the application of rule 2 . . . . . . . . . . . . . . . . . . . . . . 91 5.13 Two schemes obtained with naive grammars . . . . . . . . . . . . . . . . 96 5.14 Some generated designs (results a-f) . . . . . . . . . . . . . . . . . . . . 98 5.15 Some generated designs (results g-l) . . . . . . . . . . . . . . . . . . . . 99 5.16 Architecture of BH-ShaDe . . . . . . . . . . . . . . . . . . . . . . . . . . 104 5.17 Screenshot of BH-ShaDe interface . . . . . . . . . . . . . . . . . . . . . . 104 5.18 Shape grammar for the generation of a simple housing unit . . . . . . . 105 5.19 Housing units schemes generated with the shape grammar in Figure 5.18 106 5.20 Distribution of the total percentage of schemes of each type (A to E) . . 110 5.21 Examples of student’s project: (a) Octagonal tower and (b) Gallery . . 111 5.22 Some rules of the involved shape grammars . . . . . . . . . . . . . . . . 114 5.23 Two schemes generated without extra control mechanisms, along with their energetic evaluations . . . . . . . . . . . . . . . . . . . . . . . . . . 118 5.24 Four schemes generated using the learned policies, along with their energeticevaluations ..............................119 5.25 Sample state transition diagram. . . . . . . . . . . . . . . . . . . . . . . 130 5.26 Deep Sea Treasure problem: Environment (a) and Frontier (b) (reproduced from Vamplew et al. (2008)) . . . . . . . . . . . . . . . . . . . . . 133 5.27 Resource Gathering problem: Environment (a) (reproduced from Barrett & Narayanan (2008)) and Frontier (b) . . . . . . . . . . . . . . . . 134 5.28 Train/test performance for DST (a) and RG (b) . . . . . . . . . . . . . 135 5.29 Memory requirements (total number of stored vectors) of PQ-learning for the DST (a) and RG (b) problems . . . . . . . . . . . . . . . . . . . 135 xviii List of Figures 5.30 Deep Sea Treasure problem variants: environments for DST-2 (a), DST3(b)andDST-4(c) .............................138 5.31 Pareto frontier of the compacity-perimeter problem . . . . . . . . . . . . 141 5.32 Kinds of shape solutions for the compactness-perimeter problem . . . . 141 5.33 Train/test performance of PQ-learning applied to the compactness-perimeter problem....................................142 5.34 Shapes produced by the five policies learned in a single run of PQlearning, applied to the compactness-perimeter problem . . . . . . . . . 143 A.1 Esquema de clasificación para sistemas de diseño computacional basados en gramáticas de formas . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 List of Tables 2.1 SWOT analysis of the use of shape grammars for design . . . . . . . . . 16 4.1 Algorithm for depth-first search . . . . . . . . . . . . . . . . . . . . . . . 47 4.2 Algorithm for layered subshape detection . . . . . . . . . . . . . . . . . 53 4.3 Predefined constraints and goals provided with ShaDe . . . . . . . . . . 57 4.4 Leozscriptsummary............................. 62 4.5 Restaurant script summary . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.6 Performance measures: maximum, minimum and average generation times of Leoz design script for layered and unlayered approaches . . . . 72 5.1 Patterns yielded by one application of rule 1 to the shape in Figure 5.7 . 86 5.2 Requirement set for a single-family basic house (adapted from Montaner Muxí arquitectes (2008)) . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.3 Final state tests for every rule . . . . . . . . . . . . . . . . . . . . . . . . 91 5.4 Requirements for rules 1-9 . . . . . . . . . . . . . . . . . . . . . . . . . . 95 5.5 Rewards for every learning process . . . . . . . . . . . . . . . . . . . . . 95 5.6 Policies learnt for every rule . . . . . . . . . . . . . . . . . . . . . . . . . 96 5.7 Reward improvements gained thanks to the learned policies for every rule100 5.8 Results of Likert items . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.9 Categories, themes and supporting quotes for positive aspects . . . . . . 107 5.10 Categories, themes and supporting quotes for aspects to be improved . . 108 5.11 Requirement set for a energy efficient single-family basic house . . . . . 113 5.12 Requirement set for a single-family basic house, regarding habitability conditions and energetic efficiency . . . . . . . . . . . . . . . . . . . . . 116 5.13 Rewards for every learning process . . . . . . . . . . . . . . . . . . . . . 116 5.14 Rewards and features for the learning processes . . . . . . . . . . . . . . 117 xix xx List of Tables 5.15 Reward improvements gained thanks to the learned policies for every grammar....................................120 5.16 Evolution of estimated values over time with PQ-learning. Thicker horizontal lines indicate division between training episodes. . . . . . . . . . 131 5.17 Frontier features for the considered variants of the Deep Sea Treasure environment..................................139 5.18 Scalarized algorithm vs. PQ-learning: training steps until convergence of V(0,0),over100agents..........................139 Chapter 1 Introduction What is your definition of “design”? A plan for arranging elements in such a way as to best accomplish a particular purpose Question: Madame L’Amic. Answer: Charles Eames Design is a complex task that implies the consideration of requirements of different nature in order to attain a purpose. It involves the integration of technical, economical, social, and environmental needs, among others. Nowadays, the importance of computers along the design process is unquestionable. Computer-aided design (CAD) tools have expanded the human capabilities, providing designers with accurate mechanisms for representing, describing, visualizing, organizing and simulating design projects. In this thesis we start from the premise that computers can also play a role in the synthesis of design solutions. The term computational design has been coined for this area of research (Cagan et al., 2005), which has been accelerated thanks to advances in the understanding of what is design from a computational perspective. From a certain point of view, some aspects of the design process can be understood as a search or exploration over a space of design alternatives (Simon, 1973). The unifying thread of this thesis consists in the idea of employing artificial intelligence techniques for dealing with this design space in different manners. These techniques will have to consider design requirements of different nature, relevant to the purpose that a particular design problem seeks to achieve. In the following we describe in detail the research scope of this thesis. We also list the different contributions and explain how the thesis is organized. 1 2Chapter 1. Introduction 1.1 Research Scope This section introduces the research scope of this thesis, which moves along different areas related to computational design. As we explained before, computational design is concerned about the role of computers in non trivial aspects of the design process. Our research focuses on synthesizing new design solutions that fulfil a set of design criteria. This implies the need for techniques that can explicitly represent and generate a design space, which leads us to the area of so-called generative systems. This thesis focuses in the particular generative framework of shape grammars (Stiny & Gips, 1972), that has been widely used in the area of computational design due to its versatility. Design criteria can be directly hard-coded into the rules of a generative system, yielding an expert set of rules that always synthesizes feasible solutions. However, expert systems are usually hard to create, modify and maintain. Another alternative is the partial or total externalization of the design criteria, giving room to a more naive generative system that cannot produce feasible solutions by itself. Hence, it needs to be combined with a control method that ensures the production of good designs. In this thesis we will follow this latter approach, and will rely on different computational and artificial intelligence techniques such as search processes and reinforcement learning methods (Sutton & Barto, 1998), always from a multi-criteria perspective, as design usually implies the consideration of multiple requirements of different nature. In this thesis we delve into two different settings for combining a generative system (particularly shape grammars) with an external control method, depending on how we formalize and employ the design criteria. The first one consists in reducing the number of criteria hard-coded inside the rules, leaving some of the former to be managed in an explicit manner: we directly use them for evaluating shapes at each step of the generative process and guide it towards feasible solutions. The second setting goes one step further, and tries to use the whole set of requirements in a machine learning process that learns a heuristic. Such heuristic will determine how to apply the rules of the generative system. Hence, in the generative process we just rely on this newly discovered actuation information, so the design requirements are used in an implicit manner. 1.2 Contributions The main contributions of this thesis can be summarized as follows: 1. A classification scheme for possible approaches to computational design based on shape grammars. The different classes will depend on the nature of the involved 1.2. Contributions 3 rules, the formalization of design criteria and the external control methods 2. The development of a methodology based on the idea of encoding some of the design requirements into rules, while explicitly using others for evaluating the shapes produced along the generative process and guiding it towards good designs 3. The development of a methodology based on the idea of minimizing the design requirements encoded into the rules, and using them inside a machine learning process in order to learn a heuristic that determines how to apply the rules of the generative system 4. The application of the developed methodologies in different scenarios related to the architectural domain The contributions of this thesis have been presented in various journals, conferences, workshops and seminars. In the following we provide a list of the contributions organized by the type of publication: Journal Articles •M. Ruiz-Montiel, J. Boned, J. Gavilanes, E. Jiménez, L. Mandow, J.L. Pérez-dela-Cruz. Design with shape grammars and reinforcement learning. In Advanced Engineering Informatics, vol. 27, issue 2, April 2013, pp 230–245 •M. Ruiz-Montiel, M.V. Belmonte, J. Boned, L. Mandow, E. Millán, A.R. Badillo, J.L. Pérez-de-la-Cruz. Layered shape grammars. In Computer-Aided Design, vol. 56, November 2014, pp 104–119 International Workshops and Seminars •M. Ruiz-Montiel, L. Mandow, J.L. Pérez-de-la-Cruz, J. Gavilanes. Shapes, grammars, constraints and policies. In SHAPES 1.0 - The Shape Of Things 2011, J. Hastings, O. Kutz, M. Bhatt, S. Borgo Eds., September 2011, CEUR Workshop Proceedings, Vol. 812 •M. Ruiz-Montiel. Multi-objective Reinforcement Learning. In European Workshop on Reinforcement Learning (EWRL 11), P. Auer, M. Hutter, L. Orseau Eds., September 2013, Dagstuhl Research Online Publication Server: Reinforcement Learning (Dagstuhl Seminar 13321) 4Chapter 1. Introduction National Conferences •M. Ruiz-Montiel, J. Boned, J. Gavilanes, E. Jiménez, L. Mandow, J.L. Pérezde-la-Cruz. Proyecto arquitectónico mediante gramáticas de formas sencillas y aprendizaje. In Conferencia de la Asociación Española para la Inteligencia Artificial, November 2011 •M. Ruiz-Montiel, L. Mandow, J.L. Pérez-de-la-Cruz. PQ-learning: Aprendizaje por Refuerzo Multi-Objetivo. In Conferencia de la Asociación Española para la Inteligencia Artificial, September 2013 •M. Ruiz-Montiel, J. Boned, J. Gavilanes, P. Hidalgo, D. Belmonte, L. Mandow, J.L. Pérez-de-la-Cruz. Proyecto arquitectónico energéticamente eficiente mediante gramáticas de formas y aprendizaje por refuerzo. In Conferencia de la Asociación Española para la Inteligencia Artificial, November 2015 1.3 Thesis Outline This thesis is structured in six chapters, one appendix and a list of references. Apart from this first introductory chapter and a final one containing the conclusions and possible future work, the structure of the thesis is described in the following. Chapter 2 presents some required antecedents on computational design, shape grammars and reinforcement learning techniques. The following 3 chapters include the main contributions of this thesis. Chapter 3 classifies the different settings that can be adopted in order to combine shape grammars, control methods and design criteria. Chapter 4 presents a methodology for explicitly managing design criteria outside a non-expert shape grammar, using them for the evaluation of the produced shapes at each step of the generative process. In this setting, design criteria are divided into design constraints and goals, which are used to guide a search algorithm. We illustrate two examples in which the proposed methodology is put into practice. Chapter 5 describes a methodology that employs design criteria in order to learn application heuristics for shape grammars inside which the encoded design requirements have been minimized. Two alternatives are presented, depending on how we deal with the multi-objective nature of design problems. Namely, the first alternative starts from the premise that the problem can be scalarized according to a set of design preferences that are known a priori, thus yielding an unique heuristic for the generative system. Two application cases are presented for this alternative. The second alter- 2.1. The Problem of Computational Design 11 knowledge of the design criteria that the solutions need to meet, then the whole design space produced by such a system will be made up of valid design solutions. This implies hard-coding the design criteria into the rules of the generative system, leading probably to a great number of complex rules that are difficult to create and modify. In addition, we may be sacrificing the diversity of solutions that the system can yield, as the rules have been crafted from the preconceived idea of how the solutions must be. In the literature we can find examples of application of the aforementioned generative systems by themselves, that is, with the design criteria embedded inside their rules. For example, cellular automata have been used to generate neighbourhoods in an urban scale (Wolfram, 2002). L-systems have been used for image synthesis and modeling (Palubicki et al., 2009; Parish & Müller, 2001). Many researchers have developed shape grammars for particular design problems. Some recent examples are the works of Garcia & Romão (2015) (for designing chairs), Palacz et al. (2015) (for generating grid structures) and Kielarova et al. (2015) (for jewelry design). Graph grammars have also been employed embedding the design criteria inside their rules. For example, Siddique & Rosen (1999) proposed an approach to develop formal representations of product families and apply graph grammars to transform function structures into product structures, and applied it to a coffee-maker product family. Schmidt et al. (2000) propose a general graph grammar for structure synthesis of mechanisms, and apply it to the particular structural synthesis of epicyclic gear trains. Helms & Shea (2012) also employ a graph grammar in order to synthesize mechatronic systems. 2.1.2.2.2 Explicit Criteria. Another alternative is to deal with explicit criteria, that is, by means of a routine that takes a potential design solution as input and returns a quantitative evaluation as output. The generative system could thus be more relaxed and yield a design space with valid and non-valid solutions, and the routine would be used to perform a systematic search in which designs with a poor evaluation would be discarded. Such an explicit evaluation routine can be used even if the generative system is not automatized, that is, if is a human designer who generates the design space. This is the case of evaluative design systems, rather than generative ones. For example, Kraft & Nagl (2007) developed a prototype software providing a visual knowledge specification language for design. Graph-based domain ontologies define concepts and relations between them, as well as design rules. The designer can use the concepts and relations of this ontology in order to manually instantiate sketches of conceptual buildings, and the created sketch can then be checked against the rule base specified inside the ontology. Pauwels et al. (2011) use Semantic Web technologies in order to formalize 12 Chapter 2. Antecedents rules about building performance. The process of defining and evaluating a design concept would be similar to the one in the work of Kraft & Nagl (2007), using semantic web technologies instead of graph-based techniques. Grabska et al. (2012) developed a prototype software to support architectural design that extracts symbolic information from graphical sketches drawn by the designer. Using this symbolic information, a set of logic rules will check the validity of the sketches drawn by the designer. Some works follow this approach along with generative design systems. For example, in the work of Agarwal et al. (1999), the intermediate shapes produced by the rules of a shape grammar are measured by means of cost expressions. Bolognini et al. (2007) use rule-based spatial graph transformations in order to synthesize structural, mechanical and mechatronic systems according to a set of design constraints and termination criteria. An algorithm performs a search over a design archive that is constructed by applying the graph transformations. Wyatt et al. (2012) use elementary operations that modify schema configuration graphs, and apply a constraint-based depth-first search in order to find solutions in the context of product architecture design. Grzesiak-Kopec & Ogorzalek (2014b) use a 3D shape grammar, along with design constraints and goals, in order to solve 3D layout design problems. 2.1.2.2.3 Heuristic that Determines How to Apply Rules. Finally, another alternative is to use an heuristic that tells how to apply the rules of a relaxed generative system. Without such heuristic, the system would not yield valid solutions; by contrast, thanks to the heuristic it can generate a space of valid designs. For example, Müller et al. (2006) use shape grammars to create building mass models, and control the application of rules by means of a manually assigned priority. Other works aim at automatically learning a heuristic. For example, Cagan & Mitchell (1993) developed the shape annealing method, that guides the rule derivation of a shape grammar according to an energy function. This method can be found in several approaches like the ones of Shea & Cagan (1997), Shea & Cagan (1999b) and Shea & Cagan (1999a), and also combined with graph grammars (Schmidt & Cagan, 1997; Starling & Shea, 2005; Lin et al., 2009). Other examples can be found in the context of evolutionary programming, in which sequences of rules leading to feasible solutions are found via a fitness function (Gero et al., 1994; Jin & Li, 2007; Caldas, 2008; Wu et al., 2008). As in the previous alternative, that uses explicit routines for performing a search over the design space, shape annealing and evolutionary programming techniques also imply the definition of an evaluation routine (in the form of energy and fitness functions, respectively), but they are employed to learn an heuristic that guides the application of rules. 2.2. Shape Grammars as a Tool for Computational Design 13 2.2 Shape Grammars as a Tool for Computational Design As we mentioned in the previous section, shape grammars have been widely employed in generative computational design systems. They are a computational formalism for the generation of geometric shapes introduced by Stiny and Gips (Stiny & Gips, 1972; Stiny, 1980, 2006). Informally, shape grammars are a set of rules that govern the composition of simple geometric and symbolic elements to generate complex shapes. Shape grammars have been used in the literature for many tasks related to architectural or industrial design. In architecture, the works of Stiny & Mitchell (1978) and Cagdas (1996) have managed to devise shape grammars that capture and explain the architectural style of certain buildings, and thus create designs similar to the original ones. The work of Duarte (2005) provides shape grammars that generate designs according to a given housing program. In the context of industrial design, shape grammars have been used to design artefacts taking into account sets of design requirements. Some examples include the grammars proposed by Lee & Tang (2009a) to generate compact digital cameras, considering different combinations of form criteria; the one proposed by Agarwal et al. (1999) for the generation of coffee-makers, taking into account different cost-related aspects; and the one devised by McCormack et al. (2004) to capture a car’s brand identity. Shape grammars have also been used in the context of process planning. Brown et al. presented a method for formalising manufacturing information trough shape grammars, providing semantics such that a given derivation of the grammar can be interpreted as a process plan (Brown et al., 1996). More recently, Shea et al. (2010) developed a framework for an autonomous design-to-fabrication system that automatically fabricates customized parts ; in this framework, the shape rules encode primitive movements of the machine tool. In the following we address the formal aspects needed to understand how shape grammars work. Then, we will discuss the reasons that make shape grammars such a suitable framework for computational design, and we will describe the main kinds of shape grammars, and some existing systems that rely on them in order to produce design solutions. 2.2.1 Formal Aspects of Shape Grammars Asegment or line l={p1, p2}is defined by any pair of distinct points p1and p2, the so-called end points of the line. A shape is defined by a finite set of distinct maximal lines, i.e. lines that are not part of longer lines inside the shape. The representation of a shape is thus unique. Alabelled shape σis an ordered pair σ=hs, Piwhere sis a shape and Pis a finite set of labelled points. A labelled point (p, A)is a point pwith a symbol A. A labelled 14 Chapter 2. Antecedents shape s1is a sub-shape of another labelled shape s2(s1≤s2) if and only if every line and every labelled point of s1is in s2. Formally, a shape grammar is a tuple hS, L, R, Iiwhere: •Sis a finite set of shapes •Lis a finite set of symbols •Ris a finite set of rules α→β, where αis a non-empty labelled shape and βis a labelled shape •Iis a non-empty labelled shape, called initial shape or axiom. A rule α→βapplies to a shape γwhen there is a transformation τsuch that τ(α) is a sub-shape of γ. Usually, τis a general geometric transformation. In this work, transformations involve translations, rotations and reflections. The result produced by the application of a rule α→βto a labelled shape γunder transformation τis given by the expression γ−τ(α) + τ(β). This new labelled shape is obtained substituting some occurrence of τ(α)inside γwith τ(β). Figure 2.1 displays a rule and one sample derivation, i.e., a possible sequence of shapes generated by successive applications of the rule to an axiom γ(which in this case is a square). The first rule application detects the left part of the rule (α) inside the axiom, but under a rotation transformation τ. Hence, the right part of the rule (β) is rotated under the same transformation τ(β)and, when the expression γ−τ(α)+τ(β) is performed, the resulting shape is the second one in the derivation shown in Figure 2.1(b). When the rule is applied again, one possibility is that the small square that has appeared due to the first application is now detected, as it is exactly the left part of the rule, but scaled and rotated as well. The third time the rule is applied, the smaller square that has appeared in the third shape is detected under another scaling and rotating transformation, producing the fourth and last shape in our derivation. (a) (b) Figure 2.1: A rule (a) and one derivation starting from an initial squared shape (b) Although this derivation of rules can be performed manually, the advantage of using a computer shape grammar interpreter is obvious: the process is much faster 2.2. Shape Grammars as a Tool for Computational Design 15 and less error-prone, allowing a quick exploration of the space of designs that a shape grammar can yield. Chau et al. (2004) compared 21 implementations of shape grammars interpreters up to 2004. More recently, McKay et al. (2012) gathered some of the most relevant interpreters up to 2011. In this last review, the systems are evaluated according to a set of requirements for shape grammar implementations derived from the works of Gips (1999) and Chau et al. (2004). Most of the evaluated tools are generic in the sense that they are not aimed at a particular field of design, and provide graphic means to deal with shape rules. To the best of our knowledge, the most recent contributions in this area are the works of kang Li et al. (2009), Hoisl & Shea (2011), Trescak et al. (2012), Correia et al. (2012) and Grasl & Economou (2013). 2.2.2 Suitability of Shape Grammars to Computational Design In words of Knight (2015), “shape computations are based on perception and action. They are about seeing and drawing with basic spatial elements, using one’s eyes and hands, to make shapes. From this point of view, shape grammars ally well with contemporary theories of making in the social sciences and humanities”. In this line, shape grammars are a natural ground for computational design, in which the computer assumes the role of the eyes and hands of the designer. Also, the wide appeal of shape grammars comes from their versatility. It is well known that they are capable of producing any possible shape (Stiny, 1975). Additionally, this formalism presents specific advantages. They provide an intuitive method for shape definition. They are also compact, in the sense that they can generate sophisticated and unexpected designs with just a few rules (Rowe, 1987). As Chase pointed out, design systems based on grammars have a great potential to automate and explore many design alternatives without tedious work (Chase, 2002). These systems can help designers to focus on unexpected designs that otherwise could be easily overlooked. This potential is subject to the presence of a computer in charge of automatically, quickly execute shape grammars, as pencil-and-paper execution might be tedious and therefore useless for the sake of discovering many new solutions. Early shape grammars succeeded in capturing the essence of different architectural styles and helped to validate the formalism. However, the development of adequate methodologies to create and control the application of shape grammars when trying to achieve design goals remains an open research topic. In particular, the use of shape grammars for architectural or engineering design implies taking into consideration constraints and goals for the designed artefact. The aforementioned issues of shape grammars can be summarized by means of a 16 Chapter 2. Antecedents Helpful Harmful Internal origin Strengths -Versatility -Intuitive method -Compacity -Able to produce unexpected shapes -They can be automated in order to produce many design alternatives Weaknesses -Creation and control of SG might be difficult when trying to achieve design goals -SG execution needs considerable computational expenses External origin Opportunities -General improvement in computers’ capabilities -Increasing presence of computers in design processes Threats -Reluctance of design practitioners to use SG for their work Table 2.1: SWOT analysis of the use of shape grammars for design SWOT (Strengths, Weaknesses, Opportunities and Threats) analysis, used to evaluate the venture of choosing the technology of shape grammars for design tasks. A SWOT analysis involves identifying the internal and external factors that are favourable and unfavourable to achieve the objective, that is, the use of shape grammars for design (see Table 2.1). 2.2.3 Types of Human-SG-Design Interaction In this section we describe two different approaches on how to design shape grammars. According to Knight, “Different approaches to connecting grammars and goals have been suggested. One approach is direct. It involves writing rules with the foreknowledge that the generated designs will meet, or start to meet, given goals. In order to do this, the behaviours and outcomes of rules must be predictable in some way” (Knight, 1999, pag. 7). This approach leads to expert shape grammars, designed by a design expert such an architect or industrial designer. The other approach that Knight points out is an indirect one, in which “grammars are developed without a clear idea of their outcomes. An automated search ant test strategy is then used to explore the space of designs generated, sampling designs and testing them to see if they meet given goals”. That is, the solution space yielded by these naive shape grammars contains both feasible and infeasible designs, therefore we need an extra control mechanism in order to generate good solutions. 2.2. Shape Grammars as a Tool for Computational Design 17 In Section 2.1.2.2 we described the different ways in which design criteria can be combined with generative design systems. The first approach consists on embedding the expert knowledge inside the rules of the generative system. In this context, this is equivalent to expert shape grammars. The second and thirds approaches deal with design criteria in a different manner, leaving them outside the rules and managing them through search processes or by learning how to apply the rules in order to fulfil them. As anticipated by several examples that we provided in Section 2.1.2.2, these alternatives are amenable to be combined with naive shape grammars. In the following sections we describe the corpus of work developed in both the expert and naive approaches. 2.2.3.1 Expert Shape Grammars The execution of an expert shape grammar would lead to feasible designs, where feasibility is guaranteed by the structure of the shape grammar itself. We could call these expert shape grammars, since they include much expert design knowledge hard-coded inside their rules. There exist many references to expert grammars in the literature. Many works aim to design architectural or engineering objects in accordance with a particular style or brand identity (Stiny & Mitchell, 1978; Cagdas, 1996; Flemming, 1987; Pugliese & Cagan, 2002; McCormack et al., 2004). Figure 2.2 displays a fragment of the Palladian grammar used by Stiny & Mitchell (1978) to generate 2-dimensional plans of villas similar to those of the famous XVI century architect Andrea Palladio (see Figure 2.3). Figure 2.2: Seven rules of the Palladian grammar (reproduced from Stiny & Mitchell (1978)) Some of the methods actually used to include expert knowledge inside shape grammars comprise the following: 18 Chapter 2. Antecedents Figure 2.3: The Villa Malcontenta as drawn by Palladio (reproduced from Stiny & Mitchell (1978)) 1. Shapes in rules. This is the most direct mechanism, where desired final shapes arise from the accumulation of shapes present in the rules. 2. Control marks. Special labels added to the “real” shapes are typically used to control several aspects of rule execution, such as the order in which rules are applied, the set of rules that can be applied at a certain moment, or the way rules can be applied (i.e., transformations that can be applied to their left-hand side). A different approach is taken by Duarte in his discursive grammars (Duarte, 2005): each conventional shape grammar rule is accompanied by a description rule that uses extra symbolic information to give semantic to the involved shapes, thus allowing more control possibilities. More recently, the works of Duarte et al. have been formalized by a methodology in which several models are present: (1) a model for the formulation of a design program, (2) a model for generating designs according to the program (which is usually represented by a shape grammar), and (3) a model for evaluating solutions that is used to analyse, compare and rank alternative designs produced by the model used in (2). This methodology is applied, for example, to the generation of urban designs (Duarte et al., 2012). However, the knowledge engineering effort involved in the creation and modification of expert systems is important. Expert shape grammars, as well as rule-based expert systems in general, can become very difficult to create, modify and maintain. It is generally acknowledged that a “[. .. ]mixture of knowledge types, together with the lack of adequate justifications of the different rules, makes the maintenance of such knowledge bases very difficult and time consuming” (Studer et al., 1998). Some authors 2.2. Shape Grammars as a Tool for Computational Design 19 have given insight in the creation process of shape grammars. For example, Beirão et al. (2011) show how specific shape grammars can be created from generic ones in the field of urban design. Another approach consists on automating the creation of shape rules by means of statistical analysis (Orsborn et al., 2008) . Another issue related to the common mechanisms to introduce expert knowledge inside rules is that they promotes the use of deterministic shape grammars that tend to produce certain kind of shapes that are known a priori. A trade-off arises between the ability of a shape grammar to innovate and the feasibility of the produced solutions. In a correctly formulated expert shape grammar, any arbitrary execution of its rules will ideally produce feasible designs, since the shape grammar designer will have predicted in some way the nature of these outcomes. If we sacrifice the divergence capacity of shape grammars in the pursuit of predictability, we are at risk of missing one of the main reasons for using this formalism as a design framework, that is, the possibility of obtaining many unforeseen, innovative solutions. 2.2.3.2 Naive Shape Grammars A different approach calls for the combination of simpler shape grammars with specific methods to search the design space or guide the generation process. By simpler or naive shape grammar we understand that the design requirements are not completely hard-coded inside the rules, and thus an arbitrary execution of these rules, without any additional guiding mechanism, would not guarantee feasible designs. Naive grammars could lead to a high diversity in results, while the guidance methods would guarantee the fulfilment of design requirements. This approach avoids the usual difficulties in creating, modifying and maintaining traditional, expert shape grammars, leaving the guarantees of feasibility mainly in hands of the control mechanism. A possible alternative is to deal design criteria in an explicit manner, that is, by means of a routine that evaluates design solutions. The shape grammar could thus be more relaxed and yield a design space with valid and non-valid solutions, as the evaluative routine is used to guide the generative process towards good designs. The works of Grzesiak-Kopec & Ogorzalek (2014b); Grzesiak-Kopeć & Ogorzałek (2014); Grzesiak-Kopec & Ogorzalek (2014a) explicitly manage design constraints and goals in order to perform a search along a design space created by a 3D shape grammar. Designs that violate some constraints are discarded, and the ones that comply with them are tested according to the design goals, accepting a given design as a solution if it fulfils every goal. They apply this system to solve design layout problems. Other works seek to obtain a rule-application heuristic by means of artificial intelligence techniques such as simulated annealing or evolutionary computation. 20 Chapter 2. Antecedents Simulated annealing (Kirkpatrick et al., 1983) is a stochastic optimization technique that emulates the physical process of metal annealing, i.e. intense heating and then gradual cooling until a low-energy equilibrium state is reached. Shape annealing (Cagan & Mitchell, 1993; Shea & Cagan, 1999b) applies simulated annealing to a shape grammar derivation process. In this context, a shape that minimizes the value of a given objective function, interpreted as the energy of the shape, is sought. A set of constraints additionally determines valid transitions in the application of the shape grammar rules. At every step of rule derivation, a rule leading to a feasible new shape is randomly selected. If the new shape obtained applying this rule has lower energy than the current one, then the transition is automatically accepted. However, if the new shape has higher energy, the transition is only accepted with a probability that depends on the energy difference and the temperature of the process. Initially, when the temperature is high, the process can easily escape local optima this way. As the process goes on and the temperature is reduced, the chances of escaping deeper (low-energy) optima are reduced. In an infinite process where the temperature asymptotically approaches zero, the probability of being trapped in a global minimum approaches one. In shape annealing, the stochastic sequence of rule applications goes on until the current shape cannot be further improved after a number or trials, or a limit on the number of rule derivations is reached. The algorithm reverses rules if at a certain moment every applicable rule violates any of the constraints. The temperature profile that determines how quickly the process cools down is a critical parameter in simulated annealing. Shape annealing has been applied mainly to structural design problems such as roof truss (Shea & Cagan, 1999b,a) or dome design (Shea & Cagan, 1997). The use of shape annealing can lead to a feasible near-optimal design if the algorithm parameters are correctly configured. Apart from parameter tuning, the underlying knowledge engineering is to a great extent very easy: we just need to compute the objective function and test whether the constraints are violated. One important drawback is that each run of the algorithm leads only to a single solution. If we aim to obtain many distinct designs we have to run the optimization algorithm again and again. This approach does not learn how to generate designs, it just finds a solution each time it is executed. Genetic algorithms are an optimization technique that emulates the process of natural selection. An initial population of individuals (phenotypes) is represented as strings (chromosomes or genotype). Individuals are then selected and their strings combined to produce new individuals in a stochastic process that takes into account their fitness to a given objective function (survival of the fittest). Ideally, this iterative process produces populations with good or near-optimal individuals. Gero et al. (1994) 2.3. Reinforcement Learning 27 Figure 2.5: Watkins’s Q(λ) algorithm (reproduced from Sutton & Barto (1998)) For example, we can postulate a linear function, Q(s, a) = θ1×f1(s, a) + θ2×f2(s, a) + · · · +θn×fn(s, a) where fi(s, a)is the i-th feature of the state produced by applying action ato state s, and θiis the i-th coefficient of the function Q. The coefficients θiof this function are learned at each reinforcement learning step according to the following gradient-descent rule, that takes into account the temporal difference δ, θi←θi+α×δ×fi(s, a) The use of function approximators introduces certain complexity but, at the same time, the use of features to represent states has certain advantages. Many different states can share the same set of features, so when we update the value for a given set of features, we are learning (generalizing) over all similar pairs (state,action). Thus, if an adequate set of features is selected, proper Q-values can be learned even for states that were never visited during the learning stage. Function approximation leads to some convergence issues when it is used with a bootstrapping method (Thrun & Schwartz, 1993), especially when it is an off-policy one (Sutton & Barto, 1998). Certainly, this combination can lead to divergence and an infinite mean square error, since it tends to overestimate values. As suggested by Thrun & Schwartz (1993), the use of TD(λ) techniques rather than pure TD ones can reduce the effects of overestimation, since by means of the parameter λwe can control the level of bootstrapping. In addition, according to Thrun & Schwartz (1993), 28 Chapter 2. Antecedents Figure 2.6: A linear version of Watkins’s Q(λ) with binary features (reproduced from Sutton & Barto (1998)) imposing bounds on the discount rate can also be useful. In Figure 2.6 we can see a linear version of Watkins’s Q(λ)with binary features. 2.3.4 Multi-Objective Reinforcement Learning Most work in the area of reinforcement learning is aimed to solve MDPs with scalar rewards. However, many problems are best formulated as multicriteria MDPs where rewards are vectors, and components stands for different, possibly conflicting scalar objectives. These are usually referred to as Multiobjective Markov Decision Processes (MOMDPs). A MOMDP is defined by a set Sof states, a set Aof actions, a transition function P:S×A×S→[0,1], where P(s, a, s0)is the probability of going from sto s0when executing a, and a reward function R:S×A×S→Rn, where vector ~r =R(s, a, s0)is the expected immediate reward obtained is such case. A policy is a function π:S→A that selects an action π(s)∈Afor each state s∈S. The execution of a policy from a 2.3. Reinforcement Learning 29 given state s0leads probabilistically to a sequence of states s0, s1, . . . , si, . . . For each state stin the sequence the discounted accumulated return is given by an expected vector return ~ Rt∈Rn,~ Rt= Σ∞ k=0γk−→ rt+k+1. Different multicriteria decision paradigms can be applied to reinforcement learning. We can either start from the assumption that there exists a scalarization function than can be used to collapse the returns to a scalar value, or either from the premise that the solution is configured by a Pareto set of optimal policies. 2.3.4.1 Solving MOMDPs by Means of Scalarization Functions Roijers et al. (2013) propose a MOMDP problem taxonomy based on the first of the aforementioned assumptions, that is, that we can use a scalarization function to aggregate the vector returns into scalar values, either explicit or implicitly. This perspective is what they call the utility-based approach, as opposed to the axiomatic approach, that consists on directly discovering the Pareto front of optimal policies. The taxonomy of Roijers et al. (2013) is configured according to three aspects. Firstly, they classify the problems either as single-policy or as multiple policy. The former approach can be useful when the preferences (or relative weights) for each objective are known a priori. However, there are situations in which such preferences are not known a priori. The solution is then to find a set of so-called nondominated policies, i.e. policies that cannot improve one objective without worsening at least another one. Even in this case, scalarization functions can be used to approximate the set of optimal policies, by discovering an optimal solution for each possible weight setting. Secondly, they make a distinction according to whether the obtained policies are allowed to be stochastic or not. Thirdly, they also pay attention to the nature of the employed scalarization function, namely linear or monotonically increasing if linearity cannot be assumed. With these three criteria (single vs. multiple policies, deterministic vs. stochastic policies and linear vs. non-linear scalarization function), they propose a MOMDP problem taxonomy in which the nature of the optimal solutions for each kind of problem is characterized (see Figure 2.7). In Figure 2.7 we can see that the solutions for single-policy approaches always consist on a unique policy. If we use linear scalarization, then the resulting optimal policy is stationary. In addition, the policy is also deterministic, because, as we mentioned, for additive, infinite-horizon single-policy MDPs we can stick to deterministic, stationary policies (Boutilier et al., 1999), so we do not even need stochastic ones. However, as noticed by Roijers et al. (2013), in the multi-objective setting this does not always hold, and we need non-stationary and stochastic policies. In the 30 Chapter 2. Antecedents Figure 2.7: MOMDP problem taxonomy (reproduced from Roijers et al. (2013)) single-policy approach, when monotonically increasing functions are used and only deterministic policies are allowed, then the optimal solution is a deterministic nonstationary policy, as it can be better than a stationary one (White, 1982). If stochastic policies are allowed, then the resulting policy is in fact a stochastic one, made up from mixing two or more stationary policies. As stated by Roijers et al. (2013), in the multiple-policy approach, if preferences over objectives can be expressed by means of linear scalarization, we can also stick to deterministic stationary policies (we do not need stochastic ones, even if they are allowed), but now the optimal solution is a set rather than a unique policy. A direct approach is to use a linear scalarization function and repeatedly solve the problem with different sets of weights. The work of Castelletti et al. (2002) is one of the first approaches in this sense, tackling the problem by running a TD algorithm several times with different weights. Natarajan & Tadepalli (2005) deal with the problem in a similar manner, but reusing policies for similar configuration of weights. Other approaches aim to learn the set of policies in a parallel manner, so the weights (and thus the linear scalarization function) are implicit (Barrett & Narayanan, 2008; Hiraoka et al., 2008; Mukai et al., 2012). The set of solutions that can be calculated this way is usually called the set of supported solutions (or convex set) in multicriteria decision theory. However, in problems where the Pareto front is non-convex, it is well known that in general not all Pareto optimal solutions are supported (Vamplew et al. (2008)) If we use a nonlinear scalarization function then we can capture solutions that are missed in the linear setting. According to the taxonomy of Roijers et al. (2013), if only deterministic policies are allowed, then the solution is the whole set of non-dominated policies (that is, the Pareto coverage set), and the policies in the set need to be non- 2.3. Reinforcement Learning 31 stationary, as they can dominate stationary ones. If stochastic policies are allowed, then is enough to compute a convex coverage set of deterministic and stationary policies, since we can obtain the rest of non-dominated policies by mixing policies of this set of supported solutions. A direct approach is to explicitly use a non-linear scalarization function and, as in the linear case, repeatedly solve the problem with different sets of weights. For example, any Pareto-optimal solution can be optimal with respect to the Chebyshev norm given the adequate parameters. Some approaches using nonlinear scalarization functions in reinforcement learning can be found in the works of Shelton (2001), Vamplew et al. (2011) and Van Moffaert et al. (2013b). Nonetheless, an explicit nonlinear scalarization function might be hard to obtain. Moreover, in the particular case of the Chebyshev norm, not all optimal solutions with respect to this scalarization funtion are necessarily Pareto-optimal. Another alternative is trying to estimate sets of Pareto-optimal policies simultaneously, and thus the scalarization function would be implicit. One example is the work of Handa (2009), that combines ideas of conditional random fields, clustering, and evolutionary multi-objective optimization in a new algorithm (EDA-RL). The new method was shown to simultaneously acquire two different policies when applied to a sample MORL problem. 2.3.4.2 Solving MOMDPs by Discovering Pareto Fronts In contrast, if we start from the premise that the solution to a multi-objective MDP is the Pareto front of policies, then techniques that directly aim to find this set must be sought. In fact, we can see the aforementioned work of Handa (2009) as an approach fitting in this axiomatic perspective. Another example fitting in this approach is the work of Van Moffaert & Nowé (2014). They developed an algorithm that discovers the whole set of Pareto-optimal policies in a parallel manner, by separating the expected immediate reward from the set of expected future rewards vectors, allowing them to converge separately. The sets of policies for every (state, action) pair can be produced at execution time, performing a vector-sum of the learned expected immediate reward and the set of expected future rewards vectors. Their method can be seen as a TD extension of the multi-objective dynamic programming technique developed by White (1982), which discovered the Pareto front of non-stationary policies for an infinite-horizon MOMDP. Chapter 3 Control, Synthesis and Criteria Can the computer substitute for the designer? Probably, in some special cases, but usually the computer is an aid to the designer Question: Madame L’Amic. Answer: Charles Eames In this chapter we propose a classification scheme for possible approaches to computational design based on a particular generative system, and we use it as a framework to organize and introduce the different contributions of this thesis. In Section 2.1.2.2 we described different alternatives to combine design criteria with generative design systems. Design criteria can be (1) hard-coded inside the rules, (2) explicitly used to evaluate potential solutions and perform a systematic search of the design space or (3) used to discover a heuristic that determines how to apply the generative rules of the system. In the context of shape grammars, each alternative leads to a particular kind of shape rules, as we explained in Section 2.2.3: hard-coding design requirements inside shape rules yields the so-called expert shape grammars, while control techniques that leave the design criteria outside the rules are naturally combined with naive shape grammars. However, this separation between expert and naive grammars is not sharp, as we can establish different shades of naiveness: the more design requirements are not considered in the process of designing a shape grammar, the more the generated shapes (by the grammar itself) will divert from the ideal solutions, and thus the more naive the shape grammar can be considered. Regarding the external control processes that can be combined with generative systems, the wide spectrum of techniques described along the previous chapter (from direct search techniques to more complex methods like simulated annealing or genetic algorithms) also suggests a classification of these systems based on their sophistication. Although 33 34 Chapter 3. Control, Synthesis and Criteria Naive SG Expert SG No Control Sophisticated Control Figure 3.1: Axes for classifying different approaches combining shape grammars and control the complexity of a control method is an elusive measure, it is useful for comparing the different approaches to computational design that will be described here. In this thesis we explore different approaches that combine shape grammars and control methods used to generate good design solutions. We propose to use the two dimensions outlined in the previous paragraph in order to classify the different approaches, that is: the naiveness of the involved grammars and the sophistication of the chosen control method. We can represent this classification scheme in a graphic manner, with the help of two perpendicular axes that yield four sections, as seen in Figure 3.1. In this figure, the horizontal axis stands for the naiveness or expertness of the shape grammar(s) involved in a given system. The left end represents a totally naive shape grammar, that is, a grammar designed without considering design requirements at all. The more expert a shape grammar is, the more is located to the right, being the right end the location for pure expert shape grammars. The vertical axis stands for the complexity of the control method used in combination with the shape grammar, being the bottom end representative of non-existent guidance methods, and the top end for sophisticated control mechanisms. Design systems based on pure expert shape grammars do not need an additional control method, as the results produced by this kind of grammars are always valid. Hence, in our classification scheme, pure expert grammars would be allocated in the bottom-right corner, as seen in Figure 3.2. 35 Naive SG Expert SG No Control Sophisticated Control Expert Shape Grammars Figure 3.2: Location of a design system based on a pure expert shape grammar As we explained in Section 2.2.3, one of the main concerns about pure expert shape grammars is that they are very difficult to create and modify. Another one is their tendency to produce the same type of shapes, as the grammar designer has to foresee the outcome of the possible derivations, leading to a predictability that, while assuring the correctness of the obtained shapes, hinders diversity and the possibility of unexpected solutions. Other design systems based on more naive shape grammars can cope with these matters, at the expense of the validity of the produced shapes. To deal with this issue they need some kind of guidance method for controlling the rule application, so these systems would fall in some point located at the left of and above the point representing a pure expert shape grammar. In this thesis we propose two different computational design systems that use not purely expert shape grammars. They are introduced in the next two sections, and will be described in detail trough the rest of the thesis. In addition, in Section 3.3 we briefly describe an approach in which naive shape rules are not combined with an additional control method. Such system was developed in order to study some aspects related to randomness in design processes. 36 Chapter 3. Control, Synthesis and Criteria 3.1 Expert SGs and Sophisticated Control Shape grammars can be designed with certain level of expertness, in the sense that they can encode some, but not all, of the design requirements that solutions need to fulfil. Reducing the amount of design requirements that have to be considered inside the shape grammars can help to deal with the aforementioned issues related with the use of totally expert shape grammars. A possible approach is to divide the design requirements into two categories, one for design criteria that are easier to specify geometrically (for example, the necessity of certain shapes to be present in the solutions) and another one for design requirements that are suitable to be expressed in an explicit, symbolic manner (for example, requirements about the distance between two particular elements in the design). On one hand, the design demands falling in the first category can be naturally declared inside the shape rules. On the other hand, the needs belonging to the second group are managed in an external search process, performing an automated test over the derived shapes in order to guide the generation towards feasible solutions. In order to perform this test, we propose to use logic predicates that represent design requirements. This predicates will be divided into constraints and goals, depending on how they are managed during the search process. Every time a rule is applied, and thus a new shape is yielded, each constraint and goal is evaluated over it, obtaining true if it is fulfilled and false if it is not. The system discards those shapes that violate any of the constraints and returns a solution when, in addition to not violating the constraints, the generated shape complies every design goal. The details of the particular search algorithm used in the system will be described in Chapter 4. We also propose to enhance the shape grammars with layers, which are a very common structuring instrument in CAD tools. In our context, they can help grammar designers in the creation process, as they allow for a better visualization and a cleaner legibility of the rules. Certainly, a shape grammar designer can group different geometric elements in distinct layers, according to what they represent (for example, if the shape grammar is intended to produce house floor plans, a layer can be used for the walls, another for the doors, etcetera). The definition of constraints and goals can also benefit from this structuring device, as we can describe predicates that only refer to the geometric elements in one particular layer (for example, if we want to impose some constraints on door measures, then the associated predicate only has to check the elements inside the door layer). This system based on layered shape grammars, constraints and goals would be located in the top-right quadrant of our classification scheme (Figure 3.3), and will be described in detail in Chapter 4. 3.3. Naive SGs Without Control 43 also that in order to lead to good designs, these suggestions should not be totally aleatory, but controlled in some manner. In the following sections we will focus on the approaches falling on the top-right and top-left quadrants, where more or less sophisticated forms of controlling the chosen generative system (namely shape grammars) are used. Chapter 4 A Computational Design System for Managing Criteria in Design Problems Does the creation of design admit constraint? Design depends largely on constraints Question: Madame L’Amic. Answer: Charles Eames In this chapter we describe in detail the system advanced in Section 3.1, based on the idea of encoding some of the design requirements into rules while leaving others to be managed in an external search process employing logic predicates (Ruiz-Montiel et al., 2011b, 2014). As far as we know, this approach was the first one guiding the application of generative rules with logic predicates. The posterior works of GrzesiakKopec & Ogorzalek (2014b); Grzesiak-Kopeć & Ogorzałek (2014); Grzesiak-Kopec & Ogorzalek (2014a) also employ rules combined with predicates, in the context of layout design. A predicate is either a constraint or a goal. The search process will discard shapes that violate some constraint, and will return a solution when a shape fulfils every goal. Two are the reasons that justify the separation between design criteria that are codified inside the rules and those that are expressed as predicates. Firstly, when dealing with design problems, we can find design requirements of different nature, and it becomes clear that some of these criteria are easier to specify by means of their codification into visual rules, while others adapt better to symbolic mechanisms. The designer should be allowed to express design criteria both visually, in the form of shape rules, and also explicitly, in the form of design constraints and goals. Secondly, as the amount of 45 46 Chapter 4. A Computational Design System for Managing Criteria in Design Problems design requirements to be considered inside the rules is reduced, the shape grammars are easier to create and maintain, and they can produce more varied solutions than a pure expert shape grammar. In addition, the system allows the use of layers in order to design and visualize rules. This structuring device can help shape grammar designers in the rule creation process, as they can take advantage of the layer facilities provided by CAD tools. An additional advantage is that layers decrease the time requirements of the subshape recognition algorithm, as we can have several simple shapes separated in distinct layers instead of a complex one inside a single layer. In Section 4.1 we explain in detail the search process used to explore the design space, based on design constraints and goals, and in Section 4.2 we introduce the concept of layered shape grammars. In Section 4.3 we describe a software tool that integrates layered shape grammars with the search process. We will illustrate how the system works by means of two examples (sections 4.4 and 4.5). Finally, in Section 4.6 we discuss the performance of the system from the the point of view of time. 4.1 Constraints and Goals Our system considers logic predicates during the execution of the shape grammar. Logic predicates are boolean-valued functions that return true or false depending on whether the statement they represent is satisfied or not. We consider two kinds of logic predicates: 1. Constraints: predicates that must be satisfied at every step of any rule derivation. 2. Goals: predicates that must be satisfied at the end of any rule derivation. They control termination. The design is considered satisfactory as soon as goals are attained. In such case, the derivation sequence can terminate. The space of shapes that can be generated through the repeated application of a shape grammar to an initial shape is a directed, possibly cyclic graph with shapes at its nodes. A link connecting a shape s1to a shape s2indicates that s2can be obtained by applying some rule, with a concrete transformation, to s1. There are many links from each node as possible pairs (rule,transformation) are applicable to the corresponding shape. There are two special kinds of nodes: •Goal nodes: nodes representing a shape that fulfils all the goals, without violating any constraint. •Terminal nodes: nodes representing a shape that either does not allow more rule applications (due to its geometry), or violates some of the current constraints. 4.1. Constraints and Goals 47 Algorithm: Depth-first search (depthFirstSearch) Input: an initial shape s Output: A shape γ(if exists) that fulfils all the goals and does not violate any constraint begin if isGoalNode(s) result = s else if isTerminalNode(s) result = failure else children = getChildren(s) found = false while (notEmpty(children) and not found) child = takeChild(children) solution = depthFirstSearch(child) if isShape(solution) result = solution found = true end end if not found result = failure end end return result end Table 4.1: Algorithm for depth-first search The process of generating a shape that complies with a given set of predicates can thus be formulated as a search over this graph. In order to perform such search we could use any search algorithm. Here we use a depth-first search due to its low memory requirements and the possibility of imposing a limit on the reached depth along the search process. Table 4.1 shows the pseudo code for a recursive algorithm that performs depth-first search. The process starts at the root node of the derivation tree (see Figure 4.1), checking if it is already a goal node (with the method isGoalNode) or a terminal one (with the method isTerminalNode). Otherwise it will explore the derivation tree, descending as deep as possible along each branch before backtracking, until it finds a goal node. In case that no goal nodes are found, the algorithm will return failure. The method getChildren computes all the possible shapes that can be obtained from a given shape s, applying the rules of the shape grammar. The method takeChild takes a node of a given list and removes it from the collection. If the result of the recursive call is a shape, then the algorithm has found a solution. Otherwise, the result is failure and there does not exist any solution in that branch. Note that constraints prune the search tree, effectively reducing the space that needs to be explored. 48 Chapter 4. A Computational Design System for Managing Criteria in Design Problems  Figure 4.1: Fragment of the derivation tree for the application of the rule in Figure 2.1 Let us illustrate the use of logic predicates with a simple example over the tree sketched in Figure 4.1. Suppose that we need to produce shapes with the rule in Figure 2.1, satisfying two design requirements: 1. The shape must not contain segments larger than one meter. 2. The shape must contain at least ten squares. The user/designer has to formalize each requirement as a constraint or goal. Let us formalize the first one as a constraint and the second one as a goal. With these premises, a possible path the algorithm may follow through the tree is depicted in Figure 4.2. At the first level, the axiom (which is a one meter side square) does not violate the constraints but does not meet the goal, so the algorithm goes deeper. The same happens in the second level. In the third level, the algorithm now finds two nodes with shapes that violate the constraint, and are marked as terminal. The third shape in this level does not violate the constraints but still does not attain the goal, so the algorithm explores this node, finding a solution in the fourth level. As we have seen in this example, some requirements are specified in terms of exact metric (it is the case of the constraint, stating that the shape must not contain segments larger than one meter). Although shape grammars involve dimensionless rules in the sense that the size of the pattern to be found (that is, the left part of the rule) does not matter, these rules apply to real shapes that can in fact have dimensions, as is the case of the axiom in the previous example. Since the requirements always refer to measurable shapes, there is no conflict in establishing predicates involving exact metric. 4.2. Layers 49 X X Figure 4.2: Depth-first search of the tree of rule in Figure 2.1, with the specified predicates. Constraints need to be defined with care. When a constraint is violated, the depthfirst search algorithm prunes all the paths that could be followed from the offending node. If there were a valid solution inside some of those paths, the algorithm would never reach it. This could happen, for example, in the example depicted in Figure 4.2, if the grammar had an additional rule that removed squares. As a general guideline, a predicate can be formulated as a constraint when we are sure that once it is violated, there is no possible derivation that will satisfy it again. Otherwise, it is better to define the predicate as a goal. If the grammar contained rules that remove shapes, this property would not be present. 4.2 Layers Layers are a common structuring device in practical CAD tools. From a theoretical point of view, experts acknowledge the need of using partial descriptions of a design. Partial descriptions of designs have to be superimposed in order to make up the whole picture. A design is composed of several partial descriptions that have no meaning in themselves, that is, they are fragments of the design. They have to interact and overlap in order to form the whole meaning. Kotsopoulos, starting from the theoretical background of product shape algebras (Stiny, 1992), introduced this notion as a thinking-graphic device when working with shape grammars (Kotsopoulos, 2005). Stiny also introduced the concept of multiple tuples (or channels, as Yue and Krish- 50 Chapter 4. A Computational Design System for Managing Criteria in Design Problems namurti explain in a recent work (Yue & Krishnamurti, 2013)) in shape grammars as a technique to deal with the difficulty of distinguishing segments embedded in the maximal lines (Stiny, 1975). Here we provide an implementation for these ideas and define a new subshape detection algorithm for layered shape grammars. As we explained in the introduction of this chapter, layers allow shape grammar designers to take advantage of the layer facilities provided by CAD tools. Firstly, layers provide a cleaner visualization mode in which certain layers can be displayed or hidden in the canvas, focusing the designer’s attention on the particular segments and points that need to be dealt with at any given time. Secondly, legibility of the shape grammar can also be improved thanks to the aggregation of related segments and points into a single layer with a meaningful name. An unlayered shape grammar, in contrast, would hinder the interpretation of each segment or point. For example, a door-related segment might be mistaken for a wall, hampering further modifications of the shape grammar. 4.2.1 Formalization Formally, we define a layered shape grammar as a 5-tuple hS, L, R, I, Laiwhere: •Sis a finite set of shapes •Lis a finite set of symbols •Ris a finite set of rules α→β, where αis a non-empty layered shape and βis a layered shape •Iis a non-empty layered shape, called initial shape or axiom. •La is a finite set of nlayer names, (La0, La1,· · · , La(n−1)) A layered shape is a set of nlabelled shapes (σLa0, σLa1,· · · , σLa(n−1) ). That is, there is a labelled shape defined for each layer. In Figure 4.3 we can see an example of a layered shape (the bottom-left cross represents the origin of coordinates). A rule applies to a layered shape γwhen there is a transformation τsuch that τ(αLai)is a sub-shape of γLai, that is, τ(αLai)≤γLai, for every layer Lai. Note that the applied transformation τmust be the same in every layer. The rest of the arithmetic for labelled shapes is naturally extended to layered labelled shapes in a similar way, applying the operators in parallel to the shapes of every layer. In Figure 4.4 we can see a layered shape grammar with the content of each layer shown separately. The grammar is composed of three rules that are divided into three layers. 4.2. Layers 51 βLayer0 βLayer1 βLayer2 Figure 4.3: A layered shape (n= 3) αLayer0 αLayer1 αLayer2 βLayer0 βLayer1 βLayer2 Rule 1 → Rule 2 → Rule 3 → Figure 4.4: A layered shape grammar While defining and understanding a layered shape rule is apparently more complicated than in the case of a standard shape rule, this shortcoming can be circumvented by integrating the layered shape grammar interpreter into a CAD tool with layer facilities. These kind of tools usually allow viewing different layers separately, as well as any combination of them at once. As explained in Section 4.3, we have built our interpreter on a commercial tool that offers such layer capabilities. 4.2.2 Layered Subshape Detection Algorithm Shape grammar interpreters spend most of their time solving the so-called subshape detection problem: given two shapes αand γ, find all transformations tsuch t(α)≤γ. A reference algorithm for this problem was proposed by Krishnamurti (1981). We have extended this algorithm to the layered case. Let us start describing the original algorithm. It works with a fixed set of three points in α. This set, called DPα, is mapped to every plausible combination of three points (a so-called triplet) inside γ, and if both sets form similar triangles, then the six points are used to calculate a transformation t. If t(α)≤γ, then tis added to the solution set. The set DPαmust be carefully chosen, because the number of triplets inside γdepends on the type of points involved in DPα. For example, consider the shapes αand γin Figures 4.5 and 4.6, respectively (in this work, labels are represented by means of circles). In 4.6 we can find 22 intersection points and 4 white labels. If the 52 Chapter 4. A Computational Design System for Managing Criteria in Design Problems Figure 4.5: A shape α Figure 4.6: A shape γ set DPαis composed of three intersection points (namely, three corners of the square in Figure 4.5), then the number of triplets in γis 22 ×21 ×20. On the other hand, if DPαis composed of two intersection points (two corners) and the white label, then the number reduces to 22 ×21 ×4, so the most efficient DPαis this second one. If we have a shape γwith nlayers (La0, La1,· · · , La(n−1)), our algorithm computes all the DPs for αLai,0≤i≤(n−1). We can compute the number of triplets for every three-point set, and run the original algorithm only in the layer that requires less combinations; as the subshape relation must hold in every layer simultaneously, we can stick to one layer in order to compute all the possible transformations. Table 4.2 shows the pseudo code for this algorithm. The method getTransformations(α,β, DP) in our algorithm performs the original Krishnamurti’s algorithm (Krishnamurti, 1981) for subshape detection. The inputs for this original algorithm are shapes with presumably less points and segments than the complete shape resulting from the union of every layer, making the computation faster. In the Section 4.6 we provide a detailed analysis of time performance. 4.3 The ShaDe Tool ShaDe 1is a generative design tool that relies on layered constrained shape grammars in order to propose design solutions: it handles layered shapes that are intended to represent a design that meets a set of logic constraints and goals. In this section we focus in the architecture of ShaDe and some relevant aspects of its interface. A more detailed description can be found in the user’s guide and technical reference (Ruiz-Montiel, 2012b,a). 1ShaDe can be downloaded from http://www.lcc.uma.es/~perez/ntidapa/. 4.4. Example 1: Designing with the Hele Module 59 1 1 2 3 2 Figure 4.11: Hele Module (reproduced from (Leoz, 1978)) Figure 4.12: Some Hele Module combinations (adapted from (Leoz, 1978)) Leoz usually employed a set of predefined rooms in order to easily configure the interior space of the houses (Leoz, 1978). Since we are using two Hele modules for each housing unit, we have eight cells available to be filled with a set of rooms. The chosen set of rooms, inspired by those used by Leoz in several projects (Leoz, 1978), is depicted in Figure 4.13, with six single-cell rooms and a double one. 4.4.2 The Leoz Design Script We developed a design script in Shade to produce several distinct 2D housing units schemes, using pairs of Hele modules and the set of predefined rooms depicted in Figure 4.13. Leoz usually worked with grids that divided the plane in a regular manner. From these grids, he extracted simple shapes that were further aggregated in order to produce more complex shapes (Leoz, 1978). The Hele module comes from a rectangular grid. This grid can be used as axiom for our first production step. The subshape recognition algorithm used by the shape grammar interpreter will recognize the Hele modules inside this grid. We can now establish the layers that will reduce the computational cost of grammar execution. They will also help us to represent designs in three dimensions and to visualize different aspects of the design separately: 1. The underlying grid 60 Chapter 4. A Computational Design System for Managing Criteria in Design Problems SC LC1 LC2 DC BC1 BC2 BC3 CAPTION: SC – Service Cell (Bathrooms, kitchen and diary dining room) LC1 – Living Room Cell 1 LC2 – Living Room Cell 2 DC – Dining Room Cell BC1 – Bedroom Cell 1 BC2 – Bedroom Cell 2 BC3 – Bedroom Cell 3 Figure 4.13: Set of predefined rooms Layer0 (network) Rest of the layers Figure 4.14: The axiom for the Leoz script 2. The Hele modules yielded by the grid 3. The walls of the rooms 4. Elements with table-height 5. Elements with seat-height 6. Elements with wardrobe-height Figure 4.15 depicts the layers with the help of an example. All the shapes and rules of the grammars need to be defined for the six layers. The Leoz design script comprises three design projects, each one with its own shape grammar, constraints and goals (see Table 4.4). In the following we describe the aim of each project: •Project 1: First Hele Module. The first production step is to add the first Hele module from the axiom (see Figure 4.14). Figure 4.16 displays the single rule for this project. Labels are black in the grid layer, blue in the modules layer and white in the rooms layer. No constraints nor goals are needed. 4.4. Example 1: Designing with the Hele Module 61 Layer 5 (heigth3) Layer 4 (heigth2) Layer 3 (heigth1) Layer 1 (modules) Layer 2 (rooms) Layer 0 (grid) Figure 4.15: The layers of Leoz script for ShaDe •Project 2: Second Hele Module. Starting from the shape produced by Project 1, Project 2 adds the second Hele module. In Figure 4.17 we can see the single rule for this project. Labels are black in the grid layer, yellow in the modules layer and white in the rooms layer. A constraint is needed to ensure that both modules are in contact. We have established that two labels of the second Hele module (coloured in yellow) must be at a distance of 3.6 meters of a label from the first Hele module (coloured in blue). In Figure 4.12 we can see a small set of Hele module combinations. Thanks to the emergence properties of shape grammars, ShaDe is able to automatically generate all the combinations of two Hele modules. •Project 3: Rooms. This project adds different predefined rooms that are depicted in Figure 4.13 (the pieces of furniture are schematic), starting from the shape produced by Project 2. It has seven rules, one for each kind of room (Figure 4.18). Before the application of these rules, labels are white in the rooms layer. When rules are applied, their colors change depending on the room that is added. We need four constraints and one goal for the execution of this project: –Constraint 1: The transformations involved in subshape recognition must 62 Chapter 4. A Computational Design System for Managing Criteria in Design Problems Project Constraints Goals Execution mode 1. First Hele module - - 1 rule 2. Second Hele module (1) Hele modules in contact - 1 rule 3. Rooms (1) No scaling (2) First rule applied: service room (3) Rules are applied in order (4) Distance(service, dining) <5m (1) All rules have been applied Goals Table 4.4: Leoz script summary  network  modules rooms Rest of layers  network  modules rooms Rest of layers  Figure 4.16: Rule for Project 1 (Leoz example) not involve scaling, that is, the rooms are to be added in their original size. This constraint comes predefined with ShaDe (see Table 4.3). –Constraint 2: The first rule applied must be the one of the service cell, since it is the one that needs more space. –Constraint 3: The rules are applied in order, to make sure that every room is present. –Constraint 4: The dining room must be placed near the service room; these two rooms cannot be separated by more than 5 meters. This constraint can be configured using the coloured labels that the rules add to the rooms layer. –Goal: All the rules of the grammar have been applied. This goal comes predefined in ShaDe (see Table 4.3). This architectural example here clearly shows that some design criteria are easier to specify by means of shape rules, and other adapt better to predicates. For instance, the use of L-shaped modules is easier to elicit by means of geometric rules rather than by some kind of explicit programming. However, the fact that the two Hele modules have to be in contact is better expressed as a logic predicate: if we tried to express it by means of shape rules, we would need to configure one distinct rule for every possible combination of two modules. 4.4. Example 1: Designing with the Hele Module 63  network  modules rooms Rest of layers  network  modules rooms Rest of layers  Figure 4.17: Rule for Project 2 (Leoz example) rooms Rest of layers rooms  heigth1  heigth2  heigth3 Rest of layers Rule 1  Rule 2  Rule 3  Rule 4  Rule 5  Rule 6  Rule 7  Figure 4.18: Rules for Project 3 (Leoz example) 64 Chapter 4. A Computational Design System for Managing Criteria in Design Problems (a) (b) (c) (d) Figure 4.19: Four designs produced by the Leoz design script 4.4.3 Results We asked the tool to generate ten designs using our design script (although there is no limit to the number of designs we can ask ShaDe to generate). We show four of them in Figure 4.19. The designs satisfy the constraints and goals gathered in Table 4.4, and also present considerable variability. By specifying heights for each layer, the results can also be visualized in three dimensions. We show the housing unit of Figure 4.19(a), once the height information for every layer has been determined, in Figure 4.20. Some tools of SketchUp have been used in order to add textures and visualize it in a friendly way. 4.5 Example 2: Virtual Restaurants In this section we describe a second example that generates virtual restaurants to be used in the context of restaurant simulation video games4. This example aims to 4The script containing the shape grammars, layers, constraints and goals of this example can be downloaded from http://www.lcc.uma.es/~perez/ntidapa/restaurant-script.zip 4.5. Example 2: Virtual Restaurants 65 Figure 4.20: A housing unit with height information and textures produce more detailed solutions from the computer graphics point of view, and it also takes into account a set of requirements that are implicitly present in typical restaurant simulation video games, therefore it is oriented to provide gamers with complete (not conceptual) building solutions. Nevertheless, the produced designs can also be used as starting points in the construction process typical of this kind of video games. 4.5.1 Strategy/simulation Video Games In many strategy/simulation video games the player has to build her own world (for example The Sims,Restaurant Empire,Hotel Giant, etc.). For some users, part of the appeal comes from this construction process, whereas for others the main source of entertainment is the simulation, where they just take a predefined virtual world and start specifying the behaviour of the elements in the game. In this context, a system that automatically generates virtual worlds provides a twofold advantage: on one hand it can be used by construction-oriented gamers to obtain different starting points for their creations, and, on the other hand, it provides simulation-oriented gamers with an unlimited number of different starting points. We have developed an example related to restaurant simulation video games. Some examples of this genre are the PC saga Restaurant Empire or the Android application Restaurant Story (see Figure 4.21). 66 Chapter 4. A Computational Design System for Managing Criteria in Design Problems (a) (b) Figure 4.21: Screenshots of the games Restaurant Empire (a) and Restaurant Story (b) 4.5.2 The Restaurant Design Script In our example we consider the following elements of a restaurant building: contour, entrance door, windows, kitchen, tables, chairs and bathroom. Each element is decomposed in several layers, summing up a total of 27 layers. These will significantly reduce the computation time of the involved shape grammars, as well as allow a simple threedimensional representation with high level of detail, and a comfortable visualization of the different elements. More concretely, the following details have been included: •Walls have thickness •The buildings have main doors and windows •The furniture pieces are not box-shaped anymore. For example, the chairs have legs, seats and backs •Further additional details have been provided: columns and stairs for the main door, frames for the windows, burners for the kitchen, etc. These details are added by six shape grammars whose rules are decomposed in 27 layers. The rules are depicted in Figures 4.23 to 4.28. The design process is divided into six projects with 9 constraints and 5 goals, establishing a strong interaction between the elements so as to produce restaurants according to the implicit design rules that we can find inside a typical restaurant video game. The first project starts applying rules from the axiom depicted in Figure 4.22, and the rest of projects start from the shape produced by the previous project. Note that, for space reasons, the empty layers do not appear in the figures for the axiom and projects of the restaurant script. Descriptions, constraints and goals for the six projects are gathered in table 4.5. The script generates restaurants of 50m2with five tables and at least ten chairs, 4.5. Example 2: Virtual Restaurants 67 Layer0 (Wall labels) Walls Base Figure 4.22: The axiom for the restaurant script Wall labels Base Walls Labels Base Walls Rule 1  Rule 2  Rule 3  Figure 4.23: Rules for Project 1 (restaurant example)  Wall labels Walls Labels Walls Door box  Door column Door Step1 Step2 Step3 Rule 1   Wall labels Walls Labels Walls Window boxes Window frame  Windows Rule 2  Figure 4.24: Rules for Project 2 (restaurant example)  Wall labels  Wall labels Kitchen  Countertop Burners Larder Rule 1  Rule 2  Figure 4.25: Rules for Project 3 (restaurant example)  Wall labels  Wall labels Table legs Tables Rule 1  Figure 4.26: Rule for Project 4 (restaurant example) 68 Chapter 4. A Computational Design System for Managing Criteria in Design Problems  Wall labels Tables Tables Backs Seats Chair legs Rule 1  Figure 4.27: Rule for Project 5 (restaurant example) Wall labels Walls Wall labels Walls Base Bath window boxes Bath window frames Bath windows Rule 1  Base Door box Doors Sink Toilet back Toilet seat Figure 4.28: Rule for Project 6 (restaurant example) which are reasonable as starting points for this kind of games. Results can be further developed or improved by the players according to their preferences or game objectives. 4.5.3 Results As in the previous example, we asked the tool to generate ten designs using our design script. We show four of them in Figure 4.29. The designs satisfy the constraints and goals gathered in Table 4.5, and also present considerable variability. We show a restaurant in three dimensions, once the height information for every layer has been determined, in Figure 4.30. We can use the tools of SketchUp to add some textures and visualize it in a friendly way (in Figure 4.31(a) we can see another restaurant with textures). In Figure 4.31(b) we can see the same restaurant of Figure 4.31(a) with an automatically generated roof, thanks to the Sketchup plugin Roof Maker (Roof Maker, 2015). 4.6 Evaluation of Time Performance 4.6.1 Theoretical Analysis The original Krishnamurti’s algorithm for subshape detection (Krishnamurti, 1981) (that is, for computing all the transformations tsuch t(α)≤γ) considers all the triplets inside shape γ. When γhas npoints and all of the points inside αand γare of the same type, the number of triplets to be considered in γis P(n, 3) = (n)(n−1)(n−2) 5.1. Naive Shape Grammars and Heuristics 75 Figure 5.1: Possible solutions for the problem of generating 8-tile, compact shapes Figure 5.2: Possible intermediate 2-tile shapes It is clear that if we just apply the rule randomly until we get shapes with the desired number of tiles, then the obtained solutions are not guaranteed to be compact. We need a heuristic that, at each step, determines which is/are the better rule/s to be applied (if there is more than one good rule, then we would choose one of them randomly). One may argue that we can just use the compactness factor as heuristic to apply the rules, in the following manner: at each step, apply the rule that yields the most compact intermediate shape. If there is a draw, then choose the rule randomly. For example, if we are at the first step of the derivation process (so that we only have one tile), then this heuristic could yield any of the intermediate shapes in Figure 5.2, which are topologically equivalent and thus have the same compactness factor. Imagine that we choose the first one of these shapes. To apply the second rule, we follow the same heuristic, and thus any of the shapes in Figure 5.3 can be generated, as they are also equally compact. Following this system, a shape with four tiles setted in a row could be generated. When applying the following rule to this shape, then the outcome is analogous to the previous ones: we can either yield a L or T-shaped configuration of tiles, or a line of 5 tiles (Figure 5.4). It becomes clear that from a shape of 5 tiles in a row we cannot reach any of the optimal solutions in Figure 5.1, so we need a more informed heuristic that avoids these situations. In fact, the approach of using the set of design criteria itself as a heuristic for applying rules is somewhat equivalent to the approach described in Chapter 4, in which design criteria are directly managed through a backtracking search process. Certainly, if we undid the rule application that yielded a shape with 5 tiles in a row, we could still get an optimal solution by following another path. However, the constraints for this problem would be hard to define, as we would need to consider the particular 76 Chapter 5. Computational Techniques for Learning and Detecting Criteria in Design Problems Figure 5.3: Possible intermediate 3-tile shapes Figure 5.4: Possible intermediate 5-tile shapes configurations of tiles that cannot lead to good solutions. Defining the goal would also be tricky, as we would need to know a priori the optimal compactness factor. Moreover, a backtracking algorithm used for managing criteria in a problem with many rule applications (imagine, for example, that we want to generate shapes with forty tiles) would have huge time needs, so it would be desirable to learn a more informed heuristic to be used in a non-backtracking process. These issues suggest that the compactness factor of a shape is not a suitable design criteria to be managed in the search process proposed in Chapter 4 (at least when the shape grammar used to generate the design space is naive) and instead we should use it in a more indirect manner in order to learn a heuristic for applying the rules. One way of achieving this is by using the involved design criteria in order to define long-term rewards and then employing a reinforcement learning algorithm that learns how to take actions in order to maximize them. In the following section we explain how reinforcement learning can be applied to the framework of shape grammars, as well as the issues that arise if multiple criteria are present. 5.1. Naive Shape Grammars and Heuristics 77 5.1.1 Reinforcement Learning and Naive Shape Grammars In this section we consider the issues related to the application of a reinforcement learning technique to a shape grammar derivation process. Given a shape grammar and an initial shape (axiom), we want to obtain a heuristic that can determine which sequences of rules lead to a final shape that complies with a certain set of design criteria. In the context of reinforcement learning, this heuristic is called a policy, and is obtained by associating each possible rule application with a long-term value, learned through repeated interaction with the environment, which in this case consists of applying rules and observing the reward of the resulting shapes. Hence, the mechanism used to apply the rules is different to the one considered in Section 4, since in that particular case we did not associate rule applications to a long-term value: we performed a traditional backtracking search algorithm based on design constraints and goals. By using reinforcement learning methods we would only need to run once the learning algorithm and then use the obtained policy to apply the rules until we reach a final state. A large state space would certainly increase the time needed for the algorithm to obtain a good policy, but once it is learned, generating a solution by means of this policy would be straightforward. Moreover, as we will see in Section 5.2.1.2, we can use generalization techniques to deal with such large state spaces and thus decrease the learning time. 5.1.1.1 Shape, Rules and Design Criteria as States, Actions and Rewards Design problems usually involve more than one criteria that the solutions need to fulfil. This implies that the reward is no longer a scalar number but a vector with one component per objective. As we explained in Section 2.3.4, there are two main approaches for applying reinforcement learning techniques in such situations: the utility-based approach and the axiomatic approach. The first one relies on a scalarization function in order to treat the problem as a scalar one. The second one aims at learning the Pareto front of optimal policies. If we rely on scalarized reinforcement learning techniques, then the obtained reward is a scalar number and the design problem can be formalized as a single-objective MDP. Given a shape grammar hSh, L, Ru, Iiand a set of design criteria, the considered MDP is defined by: •S: the set of labelled shapes that can be produced by any rule sequence of the shape grammar •A=Ru ×T: the actions are the set of possible pairs (rule, τ)where τ∈Tis a 78 Chapter 5. Computational Techniques for Learning and Detecting Criteria in Design Problems geometric transformation •T:S×A→S: the deterministic transition function that determines which labelled shape is obtained when applying an action to a given labelled shape •R:S×A→R: the expected immediate reward when applying an action to a given labelled shape, defined from the set of considered design criteria A policy is a function that selects a pair (rule, τ)at each step of the derivation of a shape grammar, and it is applied from the initial state s0, which in this case is the axiom of the shape grammar. In this chapter we will use some variants of the algorithm Q-learning, described in Section 2.3. On the contrary, if we seek to discover the whole Pareto front of policies, then the design problem must be formalized as a multi-objective MDP, which differs from the previous one in the definition of the expected immediate reward: R:S×A→Rn, where now the feedback provided by the environment is a vector instead of a scalar number. In the system proposed in Section 5.2 we follow the first approach, using a linear scalarization function for the rewards. In Section 5.3 follow the second approach, for what we describe a new algorithm, PQ-learning, which is a multi-objective extension for the temporal-difference algorithm Q-learning. PQ-learning learns the whole Pareto front of non-stationary policies for a multi-objective problem. 5.2 Scalarized MORL for Design Here we propose a methodology that involves naive shape grammars as a generative system for the design space, and scalarized multi-objective reinforcement learning as a method for discovering a rule application heuristic. This methodology follows the utility-based approach proposed by Roijers et al. (2013), in which we rely on a scalarization function in order to tackle a multi-objective problem. Concretely, we use linear scalarization, and we start from the premise that the preferences over different objectives are known a priori. In the taxonomy proposed by Roijers et al. (2013), this implies discovering a single policy (see (1) in Figure 2.7). In the following we describe the proposed methodology (Section 5.2.1) and expose two application cases (sections 5.2.2 and 5.2.3). 5.2.1 The Methodology Once the naive grammars are defined (following, for example, an atomic approach like the one used in 5.1), the proposed methodology consists mainly on two tasks: 5.2. Scalarized MORL for Design 79 definition of rewards and definition of features. Here we illustrate them by means of the compactness problem described earlier in this chapter (sections 5.2.1.1 and 5.2.1.2). We also study some aspects related to the performance of the methodology applied to the compactness problem in Section 5.2.1.3. 5.2.1.1 Definition of Rewards In order to use a reinforcement learning process to discover a rule application policy, we need to develop a software routine that provides a quantitative evaluation of a potential design solution, according to the design criteria that define the problem. These routines will be used as rewards in the reinforcement learning process. In the small example introduced before we seek to obtain compact shapes. As we explained, this design criterion can be formalized with the expression area/perimeter2, which can be used to define the reward routine. Let us now suppose that we want shapes with nine tiles. The reward would be determined by means of the following expression: r(s, a) = (area(s0)/perimeter(s0)2if s0has nine tiles 0 otherwise (5.1) Where s0is the state that represents the shape generated by applying the action a over the state s. For the intermediate shapes with less than eight tiles, the reward is defined as zero, as the compactness factor of these states is not relevant. Nonetheless, a good policy will avoid the generation of shapes many tiles in a row, not because they are not compact enough, but because they cannot lead to good solutions. If more than one criteria is sought, we need a different routine for every design requirement. The reward in this case is thus a vector instead of a scalar number, so we are facing a multi-objective reinforcement learning problem. As we mentioned before, in this methodology we tackle the problem from an utility-based approach, and thus assume that we can use a scalarization function in order to aggregate the outcomes of the different routines and hence obtain a scalar reward. Here we propose the use of a linear scalarization function in order to do this, so we need a weight for every design requirement. For example, let us suppose that we also want to maximize the perimeter of the generated shapes, which leads to a situation with two utterly conflicting goals, since if we want shapes with a high compactness factor we are actually searching to minimize 80 Chapter 5. Computational Techniques for Learning and Detecting Criteria in Design Problems their perimeter. The reward could be determined by the following expression: r(s, a) = (w1×(area(s0)/perimeter(s0)2) + w2×perimeter if s0has nine tiles 0 otherwise (5.2) Where w1and w2represent the preferences over the two objectives. If more importance is given to the first goal, then w1> w2, and vice versa. Here we suppose that we know these preferences a priori, so we can just run a single reinforcement learning process with its reward defined with the help of the corresponding weights, and obtain a single policy as solution. 5.2.1.2 Generalization As we have already mentioned, working with shape grammars introduces the challenge of dealing with a vast state-action space. In these cases, using a table to store the values associated to (state, action) pairs can lead to some problems: •The large memory space requirements that such a big table would need •The large time requirements that the learning algorithm would need to learn every position of the table Generalization techniques can help to overcome these issues. First, the use of a function instead of a table reduces the memory space requirements in a drastic manner. For example, if we use a linear function, we just need to store the linear coefficients. Second, as many different shapes can share the same set of features, when we update the value for a given set of features, we are learning (generalizing) over all similar shapes. Thus, if an adequate set of features is selected, proper Q-values can be learnt even for shapes that were never visited during the learning process, representing them by means of the following expression: Q(s, a) = θ1×f1(s, a) + θ2×f2(s, a) + · · · +θn×fn(s, a) Where the coefficients θiare learned through the reinforcement learning process. There is another issue, specific to the problem of generating design solutions, that generalization techniques can help with. This is related to the desirability of obtaining diverse design solutions for a given set of criteria. If we use a table to store the Qvalues, the associated policy will produce solutions that are likely to be identical. This is due to the fact that the values of different positions of the table are probably different between them. This lack of diversity would only disappear if there were draws in some 5.2. Scalarized MORL for Design 81 positions of the table, e.g., if Q(s, a1) = Q(s, a2), that could be resolved by a random choice between the action a1or the action a2. However, although the real optimal Q-values were identical, it would probably take a long time for the learning algorithm to learn the Q-values with the accuracy needed for this sake. We could establish some threshold for comparing Q-values, but the use of generalization eliminates this problem: as many different shapes share the same set of features, their associated Q-values would also be identical, yielding the draws that we need in order to produce a diversity of solutions. In the system proposed here we will use the linear version of Watkins’s Q(λ)algorithm illustrated in Figure 2.6. As we explained in Section 2.3.3, this TD(λ) technique is more suitable to be used with function approximation than a pure TD one, given the divergence issues that arise when combining generalization methods with bootstrapping algorithms like Q-learning. Although the features of the algorithm described in Figure 2.6 are binary, in some cases our features will be real numbers ranging between 0 and 1. The expression ∀i∈Fa:e(i)←e(i)+1will then be replaced with ∀i, 1≤i≤n:e(i)←e(i)+fi(s, a), where fi(s, a)is the i-th feature of the state-action pair (s,a), and the expression Qa←Pi∈Faθiis replaced with Qa←Pn i=1 fi(s, a)θi. Let us use our small example in order to illustrate the process. The design requirement in this case is a high compactness factor (or, equivalently, a high compactness factor and a high perimeter with weights of 1 and 0, respectively). The general intuition behind the definition of the features is that they have to be related via a linear function in order to maximize the final reward. In this case, the use of a linear function of the number of modules with 1, 2, 3 and 4 neighbours makes sense, as compact shapes will probably have a certain combination of the following features: •f1(s, a) = number of modules of 1 m2with 1 neighbour in s0 •f2(s, a), f3(s, a), f4(s, a)analogously to f1(s, a)with 2, 3 and 4 neighbours respectively As these features are continuous, they will be normalized between 0 and 1, by dividing by the total number Mof modules of 1 m2that are going to exist at the end of one learning episode. In the following section we illustrate the learning process and the results obtained by applying scalar reinforcement learning to our small problem. 5.2.1.3 Performance In this section we discuss the performance of the described methodology applied to the compactness problem, regarding issues related to the learning process and the 82 Chapter 5. Computational Techniques for Learning and Detecting Criteria in Design Problems execution of a learned policy. For our geometric problem of maximizing the compactness factor of shapes with 9 tiles, the algorithm learns how much the defined features relate to each other, by discovering the θicoefficients associated with each feature fi. We have used the following configuration of parameters: α= 0.1,  = 0.3, λ = 0.5and γ= 0.8. After a particular execution of the algorithm with these parameters, the obtained coefficients are the following: θ1,1= 0.0123,θ1,2= 0.0221,θ1,3= 0.0606,θ1,4= 0.1135. For shapes with 9 tiles, the optimal accumulated reward is the one associated with a squared shape with a perimeter of 12, yielding a compactness factor of 9/122= 0.0625. As we are using a discount factor γ < 1, then the maximum reward is discounted in a factor of γ(nsteps−1), where nsteps = 8, as we have to apply 8 rules in order to get shapes of 9 tiles from the axiom. This gives us an optimal discounted accumulated reward of 0.0131. In order to evaluate the learning process, we follow a train/test perspective (Kaelbling et al., 1996), suitable when the obtained policy is to be used in an off-line setting and thus the most important factor to measure is the final quality of the learned solution, as in our case, as we do not care about the accumulated rewards obtained during the learning process as far as, eventually, the learned policy is a good one. This train/test performance is measured by executing the policies learned at certain intermediate moments of the learning process, without exploration, and registering the accumulated rewards of the obtained shapes. In our case, we take this measurement every 100 episodes. As different applications of the same policy can potentially yield different shapes due to draws between features, we execute each intermediate policy 10 times and average the obtained rewards. However, in this case the optimal policy should always produce the same shape, that is, a square of 3×3tiles. This measuring has been repeated over 10 runs of the learning process. In Figure 5.5 we illustrate the learn-test performance of the learning process. Our particular choice of parameters (α= 0.1,  = 0.3, λ = 0.5and γ= 0.8) is supported by a sensitivity analysis that was performed in order to study the robustness of the technique regarding variations of each parameter. The technique turned out to be robust for different standard values of αand . Algorithm Q(λ)also proved to be robust regarding parameter λin this domain, returning good designs for all values. A trade-off value of λ= 0.5was chosen to take advantage of the speed provided by bootstrapping methods and the safety of Monte-Carlo techniques (see Sutton & Barto (1998), Section 8.6). The algorithm was only sensitive to variations in the discount rate γ. Concretely, the algorithm did not perform well for γ= 1 (see 5.6(b)), maybe because the interactions of this rate with the convergence of the learning process, pointed out by Thrun & Schwartz (1993). The performance for γ= 0.9(see 5.6(a)) was very similar to the one for γ= 0.8(5.5). Notice that for γ= 0.9, the optimal 5.2. Scalarized MORL for Design 83 ● ●●●●●●●●●●●● ●● ●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●● 0 1000 2000 3000 4000 5000 0.000 0.004 0.008 0.012 Compacity Problem, Discount Rate = 0.8 episodes reward ● ●●●●●●●●●●●● ●● ●●●●●● ●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●Learn−test Performance Optimal Reward Figure 5.5: Train/test performance for the compactness problem accumulated discounted reward is 0.0299, and for γ= 1 is 0.0625. In order to clarify how the learnt policy guides the rule derivation process, we will go through one step of the guided application of the rule in Figure 3.4. Let us suppose that the derivation has yielded the shape in Figure 5.7. There are many possible transformation alternatives for the next application of the rule. Each transformation would yield a different shape, but many of these shapes share the same features. In order to represent all the shapes that share the same set of features, we use patterns according to the following method: we mark with a cross all the positions where one application of rule 1 could add the extra black label of its right part (see Figure 5.11). For example, in Figure 5.8 we can see the pattern for two shapes that share the following features: •f1,1(s, A)=1/M •f1,2(s, A)=5/M •f1,3(s, A)=1/M •f1,4(s, A)=2/M 84 Chapter 5. Computational Techniques for Learning and Detecting Criteria in Design Problems (a) (b) Figure 5.6: Train/test performance for the compactness problem, for different discount rates Figure 5.7: Shape with 8 tiles 5.2. Scalarized MORL for Design 91 Rule Final state test 1 Total area = 46 m2 2 Execution continues until the rule cannot be applied any longer 3 A distribution hall label exists 4 The first kitchen module is placed 5 Six kitchen modules are placed 6 The first bathroom module is placed 7 Two bathroom modules are placed 8 Two specialized labels exist 9 The entrance to the house is placed Table 5.3: Final state tests for every rule Figure 5.12: Effect of the application of rule 2 5.2.2.3 Learning Processes for Naive Shape Rules In order to generate valid designs, we must use an heuristic (policy) that determines how to apply the rules. These policies will select the most suitable transformation to be applied at each step in order to produce feasible solutions. Nevertheless, not every rule in Figure 5.11 needs the use of a policy. For example, rule 2 cannot perform badly, since it only erases residual walls that appear from the repeated execution of rule 1 (see Figure 5.12). Rule 3, which is in charge of placing the label for the distribution hall, can also perform well randomly, since when it is applied, none of the elements of the scheme has been placed yet. So this label can be placed at any point inside the scheme, and then the rest of the elements will be placed considering its situation. Rules 1, 4, 5, 6, 7, 8 and 9 need to be guided by a policy in order to perform properly, because they have to meet requirements that have not been considered inside the rules due to their naive nature. These policies will be learnt through reinforcement learning. The rewards that govern the learning process are determined from the conditions described in Section 5.2.2.1, concretely the ones in Table 5.2 and Figure 5.10. We also need to define features, because we deal with a vast state space and thus storing the value of each 92 Chapter 5. Computational Techniques for Learning and Detecting Criteria in Design Problems state in a table is not practical; therefore, we will learn a function of the features that returns the values of states. The first phase is equivalent to the geometric problem we have used previously in order to illustrate the proposed methodology, in which we seek to obtain shapes with a high compactness factor. The reward for this phase is thus this compactness measure, and the features are the same that have already been described, that is, number of tiles with 1, 2, 3 and 4 neighbours. The rewards for the learning process of rules 4-9 are defined as follows: the more requirements a state complies with at a certain step, the bigger reward it gets. An advantage of dividing the process in distinct phases is that we only have to consider subsets of requirements. For example, let us consider rule number 5, which is in charge of placing the kitchen modules. It is depicted in figure 5.11. As we can see, the rule simply states that an additional module can be placed next to an existing kitchen module. In this case, we have considered six requirements that are evaluated as 1 or 0 depending on whether they are fulfilled or not in the shape corresponding to a given state. The first one is a geometric constraint: every module must lie inside the contour. The others are direct translations of constraints imposed by the guideline Montaner Muxí arquitectes (2008): •r5,1(s)=1if every module is inside the contour. •r5,2(s)=1if every module is accessible. •r5,3(s)=1if the distance between modules and walls is bigger than 1,1 m. •r5,4(s)=1if the distance between non-contiguous modules is larger than 1,1 m. •r5,5(s)=1if the modules are at a proper distance from the distribution hall (more than 1,2 m and less than 6). •r5,6(s)=1if there are at least six modules. The scalarized reward r(s)of a state (a shape) sin the context of rule 5 is computed as the following sum: r5(s)=3∗r5,1(s) + r5,2(s) + r5,3(s) + r5,4(s) + r5,5(s) + r5,6(s) As we can see, some preferences (weights) have been used to define this reward: we have given more importance to the fulfilment of the first requirement (the one that determines if the modules are inside the contour). 5.2. Scalarized MORL for Design 93 To define the features for this phase, we have decided to identify a feature with every single requirement, so six binary features were considered for the shapes generated by this rule. Each feature is computed over the shape s0produced by applying action a to the shape of state s: f5,i(s, a) = r5,i(s0),1≤i≤6 So the learned value Q5(s, a)is determined by the function: Q5(s, a) = θ5,1×f5,1(s, a) + · · · +θ5,6×f5,6(s, a) Using this kind of features implies that states that correspond to different shapes can have the same features and thus the learning agent does not distinguish between them. The way the features are defined, sometimes a rule application may not result in a change of the features and it may seem that the agent cannot observe the immediate consequences of applying the rule. However, this just means that the rule application does not increase neither decrease the quality of the shape. As the rules that we are using are additive, the underlying shapes do change with each rule application and, in the end, a final state (which, in the previous example, is identified by the sixth feature) will be reached. The reward is defined for both intermediate and final states, and an action that does not result in a change any of the features of an intermediate state still receives a reward. Although it may seem that the quality of intermediate steps is not important, if we also reward high-quality intermediate steps (even when there are no difference in their features), then the final shapes can be better in architectural terms: it can happen that the final shape of a given execution does not comply with some criteria, but if we have favoured high quality intermediate states, then this final shape is probably nearer to a good solution than if we had not favoured these good intermediate shapes. This can be easily illustrated in the light of the previous example. Let us imagine that every kitchen module is accessible until the fifth rule application, but the last action spoils the accessibility. The second feature for the last shape is thus zero. Now imagine another rule application in which the modules were accessible only during the third first shapes in the sequence, so the second feature for the last shape is also zero. However, the first sequence of actions is better because it leads to a final shape that is nearer to our quality standards and can be easily modified to be a good one. The agent can distinguish these situations thanks to the rewards of the intermediate states and thanks to the fact that positive rewards are received even when the applied action does not result in a change of the features. In the end, the algorithm will learn the adequate coefficient θfor each feature f 94 Chapter 5. Computational Techniques for Learning and Detecting Criteria in Design Problems (that is, the policy), so as to determine which features must be pursued first in order to maximize the accumulated reward obtained at the end of the rule application. The complete set of requirements that define rewards for rules 1,4-9 is gathered in Table 5.4, and the scalarized reward expressions used for each rule are gathered in Table 5.5. All the requirements are binary, i.e one or zero when the associated predicate is satisfied or not respectively. Features for rules 4-9 have been defined according to the expression: fi,j(s, a) = ri,j(s0), as we have explained for rule 5. As we explained before, other approaches for features definition are possible (apart from directly translating design requirements). This is the case of rule 1, for which the design requirement is a high compactness factor, and we have not directly defined the features from this requirement, as in rules 4-9. Except for the first rule, for which the axiom (initial state in the learning process) is always the same (one module of 1 m2), for the rest of the rules the initial states can be quite different. For example, in the case of rule 6, the initial state is the house contour with the label of the distribution hall and the kitchen modules already placed. The distribution hall and the kitchen modules could be in many different places, so it would be illogical to always start the learning process with the distribution hall and the modules exactly in the same place. It is better to use a set of distinct initial states for every learning process. These initial states are generated by means of the previous rules, using the already learnt policies when necessary. The coefficients for each policy were initialized to arbitrary values (in our case, they were set to zero) before the learning process. After running the reinforcement learning algorithm, the values for these coefficients are learnt, with the objective of maximizing the total accumulated reward. The learnt coefficients are gathered in table 5.6. For rule 1, the learnt coefficients establish a combination of the number of tiles with 1, 2, 3 or 4 neighbours. For rules 4-9, the learnt coefficients give importance to each feature regarding the maximization of the accumulated reward. Possibly not all requirements are going to be fulfilled at the end (that is, not every feature is going to be 1-valued), so the learnt coefficients give insight to determine which requirements must be pursued first in order to maximize the final total reward. When all the policies have been learnt, we can automatically produce designs with the rules guided by their policies when these are present (that is, in rules 1, 4, 5, 6, 7, 8 and 9). In Section 5.2.2.4 we show some obtained results. 5.2. Scalarized MORL for Design 95 Rule 1 (generating the contour) r1,1(s)→the compactness factor has to be maximized Rule 4 (placing the first kitchen module) r4,1(s) = 1 if the module is at a proper distance from the distribution hall (more than 2 m and less than 4) r4,2(s) = 1 if the module is separated from the walls by at least 1,1 m Rule 5 (placing the rest of the kitchen modules) r5,1(s) = 1 if every module is inside the contour r5,2(s) = 1 if every module is accessible r5,3(s) = 1 if the distance between modules and walls is bigger than 1,1 m r5,4(s) = 1 if the distance between non-contiguous modules is larger than 1,1 m r5,5(s) = 1 if the modules are at a proper distance from the distribution hall (more than 1,2 m and less than 6) r5,6(s) = 1 if there are at least six modules Rule 6 (placing the first bath module) r6,1(s) = 1 if the module does not overlap with kitchen modules r6,2(s) = 1 if the module is at a proper distance from the distribution hall (more than 2 m and less than 4) r6,3(s) = 1 if the module is separated enough from the walls Rule 7 (placing the rest of the bath modules) r7,1(s) = 1 if the modules do not overlap with any kitchen module r7,2(s) = 1 if the modules are at a proper distance from the distribution hall (more than 2 meters and less than 4) r7,3(s) = 1 if the modules are separated enough from the walls r7,4(s) = 1 if there are at least two modules Rule 8 (labelling non-specialized spaces) r8,1(s) = 1 if in each label a 3 meter-diameter circle can be centred, without overlapping with walls or modules r8,2(s) = 1 if there is a label separated from the bath by less than 4,5 m r8,3(s) = 1 if there is a label separated from the kitchen by less than 4,5 m r8,4(s) = 1 if there are 2 non-specialized labels separated at least by 3 m r8,5(s)=1if the distance from each non-specialized label to the distribution hall label is larger than 2 m and shorter than 6 r8,6(s) = 1 if when there is one single non-specialized label, then there is enough space for another one Rule 9 (labelling the entrance) r9,1(s) = 1 if the entrance is separated by at least 1 m from every kitchen module r9,2(s) = 1 if entrance is less than 2 m from some kitchen module r9,3(s) = 1 if the entrance is separated by at least 4 m from every bathroom module r9,4(s) = 1 if the distance from the entrance to the distribution hall label is shorter than 4 m Table 5.4: Requirements for rules 1-9 Rule Reward 1 area/perimeter2 4r4,1(s) + r4,2(s) 53∗r5,1(s) + r5,2(s) + r5,3(s) + r5,4(s) + r5,5(s) + r5,6(s) 63∗r6,1(s) + r6,2(s) + r6,3(s) 73∗r7,1(s) + r7,2(s) + r7,3(s) + r7,4(s) 83∗r8,1(s) + r8,2(s) + r8,3(s) + r8,4(s) + r8,5(s) + r8,6(s) 9r9,1(s) + r9,2(s) + r9,3(s) + r9,4(s) Table 5.5: Rewards for every learning process 96 Chapter 5. Computational Techniques for Learning and Detecting Criteria in Design Problems Rule 1 θ1,1= 0,0037;θ1,2= 0,0044;θ1,3= 0,0338;θ1,4= 0,0624 Rule 4 θ4,1= 9,6338;θ4,2= 10,9915 Rule 5 θ5,1= 11,3647;θ5,2= 5,0703;θ5,3= 6,3998;θ5,4= 6,9184;θ5,5= 7,581;θ5,6= 1,7631 Rule 6 θ6,1= 13,9956;θ6,2= 10,9998;θ6,3= 10,7779 Rule 7 θ7,1= 6,7972;θ7,2= 7,2621;θ7,3= 6,8873;θ7,4= 6,8873 Rule 8 θ8,1= 6,3159;θ8,2= 2,9472;θ8,3= 7,2953;θ8,4= 5,1918;θ8,5= 7,4059;θ8,6= 8,3831 Rule 9 θ9,1= 7,4246;θ9,2= 2,0591;θ9,3= 5,7704;θ9,4= 1,5242 Table 5.6: Policies learnt for every rule Kitchen Bathroom Non-specialized space Non-specialized space Kitchen Distributor Distributor Non-specialized space Non-specialized space Bathroom (a) (b) Figure 5.13: Two schemes obtained with naive grammars 5.2.2.4 Results All tests of this application case were run on an Intel Core i7 860 @2.80 GHz processor with 8GB RAM and Windows 7 (64 bits). 5.2.2.4.1 Naive grammars without policies. A number of schemes were generated with the naive set of rules depicted in Figure 5.11, without benefiting from any process of learning. Namely, the system was used to generate 100 schemes (two of them are shown in Figure 5.13). For the final presentation of the schemes we have (1) replaced labels for the kitchen, bath, distributor hall and non-specialized spaces with suitable text, (2) replaced the entrance label with an arrow, and (3) surrounded non-specialized spaced with dotted, 3×3 m. squares. Computation was fast. The minimum generation time for a scheme was 30,42 s 5.2. Scalarized MORL for Design 97 and the maximum 41,88 s. The mean time was 34,87 s. All the schemes were different, but all of them violate several requirements of the housing program described in Section 5.2.2.1. In particular, those in Figure 5.13 violate the following requirements of Table 5.2: •R2. The contours are scattered •R3. The kitchen modules do not form a lineal space •R4. The distance between kitchen modules and walls is not higher than 1,1 m •R8. A 2,8 m-diameter circle cannot be inscribed inside each non-specialized space •R9. There is not a support space that allows the circulation between spaces. Regarding the relevant relationships gathered in Figure 5.10, these schemes do not respect them mainly because a circulation cannot be established between the different spaces in the housing unit. These results could be expected given the use of naive, non-expert shape grammars without further guidance. Grammar rules do not enforce the whole set of the involved requirements, and thus arbitrary execution is not likely to lead to feasible designs. 5.2.2.4.2 Naive grammars with policies. A hundred designs were produced by means of generation processes guided by policies when necessary (that is, for rules 1 and 4-9 in Figure 5.11). Only 11 out of these 100 schemes violated some of the constraints in Table 5.2. Therefore, compared to the ones generated by the naive grammars alone, these are closer to fulfil the housing program described in Section 5.2.2.1. We arbitrarily chose 12 schemes out of the valid ones. The generated schemes are depicted in Figures 5.14 and 5.15. Computation time was fast; the minimum generation time for a scheme was 33,94 s and the maximum 44,35 s. The mean time was 38,46 s. The slight time increase with respect to the random execution of the naive grammars is due to the calculus of the feature values, that has to be performed in this policy-driven approach, but not in the random one. Nevertheless, the number of iterations (understood as rule derivations) is the same for both approaches, as the final step tests (shown in Table 5.3) are shared. The schemes show also great design diversity. A more in-depth discussion of the quality of the results from an quantitative and architectural point of view can be found in Section 5.2.2.5. 98 Chapter 5. Computational Techniques for Learning and Detecting Criteria in Design Problems Bathroom Kitchen Non-specialized space Distributor (a) (b) (c) (d) (e) (f) Non-specialized space Kitchen Kitchen Kitchen Kitchen Kitchen Distributor Distributor Distributor Distributor Distributor Bathroom Bathroom Bathroom Bathroom Bathroom Non-specialized space Non-specialized space Non-specialized space Non-specialized space Non-specialized space Non-specialized space Non-specialized space Non-specialized space Non-specialized space Non-specialized space Figure 5.14: Some generated designs (results a-f) 5.2. Scalarized MORL for Design 99 (g) (h) (i) (j) (k) (l) Kitchen Non-specialized space Distributor Non-specialized space Bathroom Non-specialized space Distributor Kitchen Bathroom Non-specialized space Non-specialized space Distributor Kitchen Bathroom Non-specialized space Non-specialized space Distributor Bathroom Kitchen Kitchen Kitchen Distributor Non-specialized space Non-specialized space Bathroom Bathroom Distributor Non-specialized space Non-specialized space Non-specialized space Figure 5.15: Some generated designs (results g-l) 100 Chapter 5. Computational Techniques for Learning and Detecting Criteria in Design Problems Rule Reward Improvement 1 2.452 4 2,2222 5 2.1667 6 1.1904 7 1.2174 8 1.6 9 1.8182 Table 5.7: Reward improvements gained thanks to the learned policies for every rule 5.2.2.5 Discussion The results shown in section 5.2.2.4 can be discussed from several points of view. We will focus on the following issues: 1. Admissibility of generated schemes 2. Architectural evaluation of the generated schemes 3. Variability of generated schemes and generation times 5.2.2.5.1 Admissibility of generated schemes. The first goal of the system should be to generate admissible designs according to the Montaner program (that is, regarding the items in Table 5.2 and the relationships depicted in Figure 5.10). Obviously, a naive grammar generates inadmissible schemes: it is difficult for a scheme generated at random to satisfy all the requirements. It was illustrated in Section 5.2.2.4.1. However, when policies are learnt the rules generate better designs, as the rewards considering Montaner criteria are maximized. Regarding conditions of Table 5.2 and Figure 5.10, we found that in the set of the 100 generated housing units, the requirements were violated only 22 times. In terms of the obtained rewards, we have measured the average reward improvement that is gained thanks to the learned policies. For each rule ithat can be combined with a policy, we denote Rias the average accumulated reward obtained when the rule is applied randomly, and R∗ ias the average accumulated reward obtained when the learned policy is used to guide the rule application. The reward improvement for the rule iis then represented by the expression R∗ i/Ri. The reward improvements for every rule in this application case are gathered in Table 5.7. 5.2.2.5.2 Architectural evaluation of the generated schemes. The results in Figures 5.14 and 5.15 were studied by a team of architects. From the depicted set of schemes, two were chosen by the architects as the best alternatives, and other two ones 5.2. Scalarized MORL for Design 107 1 2 3 4 5 6 MEDIAN MODE (Q1, Q3)Don’t agree Agree About the software tool... 1. I quickly learned how to use the tool 0 3 4 3 41 27 5 5 (5,6) 8,97% 91,03% 2. It was easy for me to use the tool 0 0 2 10 32 34 5 6 (5,6) 2,56% 97,44% 3. The user interface is intuitive 1 3 12 30 20 12 4 4 (4,5) 20,51% 79,49% 4. The tool worked quick enough 1 4 17 24 22 10 4 4 (3,5) 28,21% 71,79% 5. The tutorial was easy to follow and useful 1 3 8 11 36 19 5 5 (4,5) 15,38% 84,62% About the schemas proposed by the tool... 6. They can be helpful in the design process 4 12 17 27 14 4 4 4 (3,4) 42,31% 57,69% 7. They can provide good starting points 2 9 8 25 29 5 4 5 (4,5) 24,36% 75,64% 8. The schemas were interesting 3 7 19 24 21 4 4 4 (3,5) 37,18% 62,82% 9. The diversity of the schemas generated was sufficient 5 17 13 18 17 8 4 4 (2,5) 44,87% 55,13% 10.The schemas were innovative 3 18 25 17 12 3 3 3 (2,4) 58,97% 41,03% 11.The schemas were reasonable from an architectural point of view 6 19 28 19 6 0 3 3 (2,4) 67,95% 32,05% Global Evaluation 12.It was easy for me to create a dwelling in which I would like to live 5 15 17 24 15 2 4 4 (3,4) 47,44% 52,56% 13.Without the tool, this practice would have been more difficult 6 17 17 14 18 6 3 5 (2,5) 51,28% 48,72% 14.I would like to know more about this kind of tools 3 3 24 29 8 11 4 4 (3,4) 38,46% 61,54% 15.I would like to be able to define my own shape grammars 0 19 21 19 11 8 3 3 (3,4) 51,28% 48,72% 16.I would like to use this tool in the future 4 17 22 21 9 5 3 3 (2,4) 55,13% 44,87% 17.I would recommend the use of this tool to my classmates 6 16 24 16 10 6 3 3 (2,4) 58,97% 41,03% About this practice 18.All in one, it was interesting 3 5 7 27 29 7 4 5 (4,5) 19,23% 80,77% 19.I think that the methodology used was suitable 1 3 15 26 25 8 4 4 (4,5) 24,36% 75,64% 20.It was rewarding to work in groups 1 3 12 13 26 23 5 5 (4,6) 20,51% 79,49% Table 5.8: Results of Likert items CATEGORIES Name №answers %answers THEMES EXAMPLES OF SUPPORTING QUOTES Diversity 26 19,26% ASPECTS RELATIVE TO QUALITY OF SOLUTIONS (25,18%) “Great variety of alternative solutions” “What I liked most about this practice is that I could develop a feasible project” “The tool provides a great variety of cells, some of them present little annex spaces that could be grouped generating unexpected solutions” Validity 6 4,44% Versatility for groupings 21,48% Usability 32,22% Efficiency 10 7,41% Possibility of using software tools in the design process 32,22% ASPECTS RELATIVE TO THE SOFTWARE TOOL (11,85%) “The tool was easy to use” “The tool generated the schemas quickly and I could take good advantage of some of them” “Being able to use new computational methods for architectural design based on randomness” Possibility of working in groups 10 7,41% TEAMWORK (14,82%) “Working in groups and new relationships with other students” “Debates in the group about what is desirable or not in architectural design” Processes of selection/reflection carried out in the working groups 10 7,41% Randomness 96,67% Happy accidents or bugs 3 2,22% Provides starting points 41 30,37% 135 different answers Overcoming preconceived solutions 12 8,89% CREATIVITY (48,15%) “The tool provides a degree of randomness that would be otherwise difficult to include in a project” “Little annex spaces that appear accidentally can be used to generate diverse groupings” “Being able to have an starting point instead of a blank page” “The tool generates schemas that you would not think of” Table 5.9: Categories, themes and supporting quotes for positive aspects 108 Chapter 5. Computational Techniques for Learning and Detecting Criteria in Design Problems CATEGORIES Name №answers %answers THEMES EXAMPLES OF SUPPORTING QUOTES Software capabilities for edition 98,82% ASPECTS RELATIVE TO THE SOFTWARE TOOL (12,74%) “The user should be able to modify some aspects of the schemas generated” “A more intuitive interface” Usability (interface) 4 3,92% Shape grammar should include additional criteria 20 19,61% ASPECTS RELATIVE TO SHAPE GRAMMARS (21,56%) “Shape grammars should include additional architectonic criteria” “To fully exploit the tool, the user should be able to define his/her own shape grammars” Possibility to include user-defined shape grammars 21,96% Overlapping of non-specialized spaces 11 10,78% ASPECTS RELATIVE TO DISTRIBUTION OF SPACES (17,64%) “Overlapping of non-specialized spaces should be avoided” “Some kitchen modules are inaccessible” “The tool should not generate residual spaces” “The location of the entrance door near to the kitchen constraints the variety of the solutions” “Better distribution of spaces” “Wet zones should be contiguous” Bad distribution of kitchen furniture 32,94% Residual spaces 10 9,8% Better location of doors 12 11,76% Better distribution of spaces 32,94% Better placement of wet zones 10 9,80% 102 different answers Excess of randomness 98,82% ASPECTS RELATIVE TO THE SOLUTIONS (48,03%) “The randomness of the tool should be controlled” “Greater variety of schemas generated” “Other parameters should be considered (environment, social aspects, etc.) ” Poor variety of solutions 76,86% Additional criteria should be considered (not only architectonic) 21,96% Table 5.10: Categories, themes and supporting quotes for aspects to be improved Now we will use the presented results to analyse to what extent the starting points provided by BH-Shade have been useful for the students in the early stages of their design projects. With respect to this question, probably the more useful Likert items are items number 6, 7 y 8. In particular, item number 7 is very relevant, and we can see that 75,64% of the students agree that “The schemes provided by the tool can provide good starting points”. In addition, the students seem to agree that “The schemes were interesting” (62,82%), and that “The schemes can be helpful in the design process” (57,69%). This same conclusion can be reached from the analysis of the positive aspects of the first free-text item. Indeed, the theme “Starting Points” spontaneously emerged from student answers, being mentioned by 48,15% of the students, and specifically 30,37% of them mentioned that “The tool provides good starting points”. In this theme, other aspect mentioned by 8,89% of the students was the possibility of overcoming preconceived solutions. Teacher’s feedback also seems to support this conclusion, because they said that “However, the most interesting projects have emerged from accidental elements like annex spaces or errors”. In fact, and according to their experience, “the designs of the clusters of schemes obtained using traditional methods are usually more rigid and less creative that the ones generated with the tool”. Continuing with the positive aspects of the tool, the next more frequently mentioned theme in the survey was “Aspects relative to the quality of solutions” (25,28%), and 5.2. Scalarized MORL for Design 109 in particular, the category “Diversity” (19,26%). As for the teachers, they declared that “the program generates such high variety of schemes that accidents occurred randomly, giving birth to what at first sight could be considered as undesirable forms, but finally generate the most interesting projects”. With respect to the tool, the students emphasized (7,41%) its “Efficiency” (also the teachers said “The tool expedited the design”). All in one we think that, according to both the teachers and the students, the stronger point of BH-ShaDe is its capability to generate an unlimited number of diverse, feasible, random and suggestive starting points for novice designers. With respect to aspects to be improved (and focusing our discussion in the quality of the starting points provided), the most frequently mentioned theme was “Aspects relative to distribution of spaces” (48,03%), and specifically the categories “Better location of doors” (11,76%), “Overlapping of non-specialized spaces” (10,78%), or “Better placement of wet zones” (9,8%). Next more frequently mentioned theme was “Aspects relative to Shape grammars” (21,56%), in particular, the category “Shape grammars should include additional criteria” (19,61%). 5.2.2.6.2 Teacher’s opinion. Three architecture teachers participated in the experiment. One of them was a member of our research team, while the other two did not have previous knowledge of shape grammars or about the tool. We developed a small survey for these two teachers, which had four open questions. For space reasons we do not include their complete answer, but a brief summary of the more relevant information. It seems that what the teachers liked most of this experience was the possibility to use this kind of tool and learn about shape grammars, together with the interdisciplinary work carried out by the research team and the fact that the tool can provide an unlimited number of schemes, and therefore expedite the design process. Overall, they said that the students had done a great job, and that the more interesting projects emerged from the accidental elements, like the little annex spaces generated in some of the automatic solutions presented by the software tool. More concretely, they said that “The tool expedited the design process. The most interesting projects have emerged from accidental elements, like annex spaces or errors. Initially, they seemed not to have any practical use, buy finally they have served to encourage the clustering of the dwellings, and have provided support so the students could freely use their imagination. We do believe the tool has accelerated this kind of discoveries". They also pointed out that the use of tool has provided an excellent exercise of analysis and reflection. The students have learned in a practical way that their preconceived ideas are not always the best ones.“Having 81 housing plan floors automatically generated by the tool, so they could be discussed and selected by the groups of students, has been an excellent exercise about analysis/reflection, which is 110 Chapter 5. Computational Techniques for Learning and Detecting Criteria in Design Problems Figure 5.20: Distribution of the total percentage of schemes of each type (A to E) usually easier to carry out in other people’s work than in our own designs. At the same time, the program generates such a wide variety of schemes that accidents occurred randomly, giving birth to what at first sight could be considered as undesirable forms, which finally generated the most interesting projects. Students have therefore learned in a practical way that their preconceived ideas are not always the more appropriate solutions". As for possible improvements, they mentioned that it would be useful to include more architectural criteria in the shape grammars defined. “In relation to the tool and its use in this particular activity, we think that it would be desirable to extend the number of variables to be taken into account in the shape grammar". 5.2.2.6.3 Students’ Final Projects. In the last session of the experiment, groups of students presented their final projects. Each group presented A1 sheets with the 81 schemes, evaluated from A (no changes needed) to E (the scheme is absurd). In total, there were 9 groups of 81 schemes. The distribution of the percentage of schemes classified according to the different grades (both among those produced by the students and among those generated automatically by BH-ShaDe) is shown in Figure 5.20. In their presentations, the students stated that they had held very productive discussions to agree about criteria to classify schemes (recall that teachers also thought that this discussion/reflection process had been very productive). To this respect, some groups had established more demanding criteria than others. The teachers pointed out that some of them had discarded useful schemes for irrelevant reasons, such as a poor positioning of some elements (door, kitchen/bath furniture) or the superposition of non-specialized spaces. The high number of schemes classified with D and E can be explained by the fact that the students considered criteria (circulation, ventilation, light distribution or grouping of wet zones) not accounted in the guideline used by the tool. 5.2. Scalarized MORL for Design 111 (a) (b) Figure 5.21: Examples of student’s project: (a) Octagonal tower and (b) Gallery From the schemes classified with A or B, each group selected four or five as the basis to create more complex structures. They explored different kinds of groupings: single-family houses, apartment blocks, galleries, etc. There were many interesting projects, for illustration purposes we will show two of them (selected by the teachers as illustrative for different criteria) in Figure 5.21. The teachers selected the first project as representative of those than emerged from starting points that contained accidental elements (and finally gave birth to creative solutions). This group used one of the schemes generated by the computer, even when it had two small corridors next to non-specialized spaces. The students decided to use these two small corridors as terraces to generate an octahedron tower. The second project was chosen because it illustrated a nearly feasible solution (in teacher?s words, it seemed nearly pre-conceived). The students selected this scheme among those generated by the computer because it has a good distribution of the so-called wet zones (kitchen and bathroom). In this way, once the schemes are grouped, the wet zones occupy the central part of the building. Overall, it seems that both the teachers and the students think that the inclusion of additional architectural criteria (circulation, ventilation, illumination, grouping of wet zones...) could improve the quality of the solutions provided. Finally, and in relation with the overall quality of the starting points, Figure 5.20 shows that the students gave higher scores to their own designs than to those generated automatically by the tool. 5.2.3 Application Case 2: Generation of Energy-Efficient Housing Unit Designs In this section we extend the previous application case by adding design requirements related to energy consumption. Now we seek to generate schemes of habitable and energy efficient housing units (Ruiz-Montiel et al., 2015; Hidalgo et al., 2015). Some 112 Chapter 5. Computational Techniques for Learning and Detecting Criteria in Design Problems previous works also rely on shape grammars to produce energy efficient design solutions: Caldas (2008) uses generative rules along with evolutionary algorithms to generate energy-efficient architecture solutions, and Granadeiro et al. (2013) converts a shape grammar into a parametric design system able to yield envelope shapes that can be evaluated by means of an integrated energy simulation software. Certainly, research on energy efficient buildings is currently on demand, starting with designs that consume the least amount of natural resources and produce a minimum of residual materials along their life cycle. Behling distinguishes between active systems,passive systems and the architectonic form itself as central elements in the thermodynamics of a building (Ábalos, 2008, 2012). The first ones control the energy interchange in the building by means of mechanic devices with a high energy consumption (such as ventilation, heating and air conditioning systems). On the contrary, passive systems are elements added a posteriori, in top of the architectonic form, that do not need from a mechanic action (like covers, projections, fronts or sunshades). Finally, the architectonic form favours an adequate energy interchange in a passive way, but it is projected a priori. The traditional methodology consists on emphasizing the technology of active energy-saving systems. This technology is usually superimposed to passive systems, that are consequence of a choice of architectural forms where sustainability has been disregarded. Behling (2012) proposes to invert the relative importance of these systems, so active ones have a residual importance and thus the process of selecting shapes guarantees the sustainability of the project. 5.2.3.1 Energy Efficient Housing Unit Design In order to generate energy-efficient housing units we have considered a set of good design practices that can be found in several guides and research works (Enerbuilding, 2008; Passivhaus, 2011; Pacheco et al., 2012). These criteria, defined in the climatic context of Spain, can be classified into three categories: 1. Contour-related criteria: according to Pacheco et al. (2012), passive design techniques usually imply the maximization of both the compactness of the contour and the portion of the façade oriented to the south 2. Inner spaces criteria: according to the Passivhaus Standard (Passivhaus, 2011), the orientation of the different inner spaces of the house can affect to its energetic efficiency. For example, the living room might works better oriented to the south due to the adequacy of this orientation throughout the whole day, during both summer and winter; and the bedroom can benefit from an east orientation, as it allows to get advantage of the natural light of the sunrise in order to wake up 5.2. Scalarized MORL for Design 113 Global requirements R1: Total area must be of at least 48 m2 Habitability requirements R2: There must exist two non-specialized spaces, a kitchen, a bathroom, a distributor space and an access to the housing unit R3: Spaces must not overlap R4: Distance requirements extracted from Figure 5.10, where two spaces are here considered to be adjoining if the distance between them is not greater than 4 meters Energy efficiency requirements R5: The contour must be compact R6: The proportion of the façade oriented to the south (south-oriented perimeter/- total perimeter) has to be maximized R7: Non-specialized spaces must be south or east-oriented R8: The total glazed surface must represent a minimum percentage of the total façade. Such percentage depends on the compactness factor of the contour: if the perimeter is greater than 40 meters, and hence we have a low compactness factor, the percentage will be 25%. Otherwise, this percentage will be 30% R9: Every space must have an associated window R10: The glazed surface oriented to the south must represent at least the 40% of the total south façade R11: The glazed surface oriented to the south must represent at least the 40% of the total glazed surface R12: The glazed surface oriented to the west must represent at most the 20% of the total glazed surface Table 5.11: Requirement set for a energy efficient single-family basic house 3. Window-related criteria: according to the Enerbuilding guide (Enerbuilding, 2008), the amount of glazed surface oriented to the south must represent a significant percentage of the total façade Regarding the design criteria related to the habitability of the housing units, here we have considered a similar set of requirements to those considered in the previous example, but simplified. The whole set of considered criteria are gathered in Table 5.11. Here we consider some additional requirements that are not mentioned in the guidelines, but have a considerable architectonic relevance: non-specialized spaces must have an associated window, and the amount of glazed surface oriented to the west has been limited. 5.2.3.2 Naive Grammars and Phases of Generation The generation process for producing energy-efficient, habitable housing units has been divided into four phases: 1. Generation of the contour 2. Placement of the different spaces in the housing unit 3. Placement of the windows 114 Chapter 5. Computational Techniques for Learning and Detecting Criteria in Design Problems Grammar 1 A rule of the grammar 2.1 A rule of the grammar 2.2 A rule of the grammar 2.3 Two rules of the grammar 2.4 Two rules of the grammar 3 Two rules of the grammar 4 Figure 5.22: Some rules of the involved shape grammars 4. Grouping of contiguous windows As in the previous application case, each phase is associated to a particular shape grammar and a particular set of design criteria. In Figure 5.22 we illustrate the some rules of shape grammars used in this case. The complete set of rules can be found in the technical report that describes in detail this application case (Hidalgo et al., 2015). For each grammar, a termination condition is established, in order to decide when the application of the rules must stop. In the following we detail the necessary steps for synthesizing a housing unit scheme: 1. The production of a scheme starts with an axiom defined by a rectangle of 6×4 meters. Starting from this shape, the rule of the grammar 1 is applied until reaching a contour of 48m2 2. The second phase consists of four grammars: the first three (grammars 2.1, 2.2 and 2.3) place the necessary spaces of the house, by adding different labels. Each one of these grammars is applied once, by picking up one of their rules, over the shape synthesized by grammar 1. Grammar 2.4 is used over the shape produced by the grammar 2.3, and contains rules that move the placed spaces. These rules 5.2. Scalarized MORL for Design 115 are applied until the design criteria related to the second phase are met or until a limit of 50 rule applications 3. The third phase places the windows applying the grammar 3 over the shape synthesized by the grammar 2.4. Rules of grammar 3 are applied until the total glazed surface is greater or equal to a given percentage of the total façade. Such percentage depends on the compactness factor of the contour. We work with three types of windows: south-oriented, north-oriented and east/west-oriented, each one with different protection elements 4. The fourth phase regroups the windows transforming them into large windows of porches, applying grammar 4 randomly over the shape produced by grammar 3 In Figure 5.23 we show two schemes generated by means of this sequence of steps, without using any rule heuristic that tells which rules are better to apply. That is, the rule that is applied at each step is picked up randomly. As we will discuss in Section 5.2.3.4, these schemes are not actually admissible, highlighting the need for rule application heuristics in order to comply with the considered housing unit requirements. 5.2.3.3 Learning Processes for Naive Shape Rules In order to get good solutions we need to learn policies for phases 1, 2 and 3. Concretely, the grammars that will benefit from this learned policies will be grammars 1, 2.4 and 3. These policies will decide which rule and transformations are better to apply at each step, with the goal of synthesizing valid designs regarding the design criteria gathered in Table 5.12. The fourth phase does not need such a policy, because we consider that every generated group of windows is admissible. In Table 5.12 we describe in detail the whole set of considered design criteria (related to both energetic efficiency and habitability) that are sought in this example, classified according to the grammar for which they will be considered. The rewards for the learning processes of each grammar are defined in terms of the requirements gathered in Table 5.12. They are described in Table 5.13. The features for every grammar are detailed in Table 5.14. Once the policies are learned, they will be used to guide the generative processes by choosing between different combinations of features. For example, for grammar 2.4, the features are based on the distance between pairs of spaces. What a policy for this phase can learn is which ranges of distances for each pair are more suitable in order to attain the most habitability and efficiency requirements. 116 Chapter 5. Computational Techniques for Learning and Detecting Criteria in Design Problems Requirements Grammar 1 R1-1: The total surface of the housing unit must be at least of 48 m2 R1-2: The compactness factor of the contour (area/perimeter2) has to be maximized R1-3: The proportion of the façade oriented to the south (south-oriented perimeter/- total perimeter) has to be maximized Requirements Grammar 2.4 R2-1: There must exist two non-specialized spaces, a kitchen, a bathroom, a distributor space and an access to the housing unit R2-2: Spaces must not overlap R2-3: Distance requirements extracted from Figure 5.10, where two spaces are here considered to be adjoining if the distance between them is not greater than 4 meters R2-4: Non-specialized spaces must be south or east-oriented Requirements Grammar 3 R3-1: The total glazed surface must represent a minimum percentage of the total façade. Such percentage depends on the compactness factor of the contour: if the perimeter is greater than 40 meters, and hence we have a low compactness factor, the percentage will be 25%. Otherwise, this percentage will be 30% R3-2: Every space must have an associated window R3-3: The glazed surface oriented to the south must represent at least the 40% of the total south façade R3-4: The glazed surface oriented to the south must represent at least the 40% of the total glazed surface R3-5: The glazed surface oriented to the west must represent at most the 20% of the total glazes surgace Table 5.12: Requirement set for a single-family basic house, regarding habitability conditions and energetic efficiency Grammar Reward 1 The reward is a weighted sum of requirements R1-2 and R1-3, normalized between 0 and 1. In case this sum is greater than 0.8, the reward is truncated to 1, in order to favour variability 2.4 Each individual requirement extracted from R2-2, R2-3 and R2-4 is evaluated to 1 or -1 depending on whether it is fulfilled or not, respectively. The reward is a weighted sum of these evaluations 3 Each individual requirement extracted from R3-2, R3-3, R3-4 and R3-5 is evaluated to 1 or -1 depending on whether it is fulfilled or not, respectively. The reward is a weighted sum of these evaluations Table 5.13: Rewards for every learning process 5.3. Pareto MORL for Design 123 performs an action an, observes the following state s0, receives an immediate reward −→ rnand adjusts the set Q(sn, an)using a learning factor αn. Therefore, the essence of PQ-learning is described by an updating expression, in many senses analogous to the one of Q-learning. The basic idea behind the updating procedure of PQ-learning is that a non-dominated action-vector must result from the combination of non-dominated action-vectors associated to the same policy. Since PQ-learning learns all non-dominated policies at the same time, the Q(s, a)sets store different vectors estimates. Each estimate arises from the combination of a set of non-dominated state vectors of states s0reached after action a. The scalar Q-learning algorithm calculates action values Q(s, a)combining the state values V(s0)of states s0reached after performing action ain state s. In the case of PQlearning, we have sets of state-vectors V(s0), defined as the set of nondominated actionvectors for all possible actions in state s0. Each of these state-vectors is associated to a different policy. Each action vector in Q(s, a)will result from the combination of particular state-vector estimates of reached states, and should always be updated according to them, reflecting thus a particular policy. Formally, each vector estimate in Q(s, a)will consist of a pair (~q, P), where ~q is the current value of the vector estimate, and Pis a set of indices. Each index p∈P is a pair (s0, i)where s0is an identifier of the accessed state and istands for the i-th vector in V(s0), precisely the one that is used to update ~q. Notice that the dimension of ~q, given by the number of objectives, is fixed and the same for every state. However, the size of Pcan be different for different states and grows during the execution of the algorithm from 0to the number of states reachable from safter performing action a. We will say that a pair (s0, i)is new for a set Q(s, a)when there is no pair (~q, P)∈ Q(s, a)such that (s0, i)∈P, and write (s0, i)6@Q(s, a). Otherwise we will say that (s0, i)is not new in Q(s, a)and write (s0, i)@Q(s, a). We will say that a state s0is new for a set Q(s, a)when there is no index isuch that (s0, i)@Q(s, a). We will write s06@Q(s, a). Otherwise we will say that s0is not new in Q(s, a)and write s0@Q(s, a). We also define the set P\s0as the result of removing all pairs (s0, i)from P, that is, P\ {(s0, i)}(whatever iis). We will formally define the sets V(s)in function of the vector estimates (this definition is similar to the one used by White (1982) and Wiering & de Jong (2007)): V(s) = ND [ a∈A {~q |(~q, P)∈Q(s, a)}(5.3) We can identify two different kinds of operations in the updating process of Q(s, a), 124 Chapter 5. Computational Techniques for Learning and Detecting Criteria in Design Problems 1. Creating new vector estimates every time a state s0is reached for the first time after performing action ain state s. 2. Updating Q(s, a)after an already traversed transition leading to some node s0. This includes updating, creating, and deleting particular vector estimates. We assume that for all s∈Sand for all a∈A,Q0(s, a) = {(~ 0,∅)}. The updating expression for PQ-learning is, Qn(s, a) = (Nn−1(s, a)∪Un−1(s, a)∪En−1(s, a) if s=sn∧a=an Qn−1(s, a) otherwise (5.4) In the following we define the sets N,Uand Edepending on the kind of operation that is being performed. •Case 1. When a state s0is reached for the first time from state sthrough action a, every vector estimate in Qn−1(s, a)is updated with every vector estimate inside Vn−1(s0), performing a pairwise update. If Vn−1(s0)only has one vector estimate, then |Qn(s, a)|=|Qn−1(s, a)|. In general, when s0is reached for the first time, |Qn(s, a)|=m|Qn−1(s, a)|, where mis the number of vector estimates inside Vn−1(s0). More formally, Nn−1(s, a) = {((1 −αn)~q +αn[~rn+γ~vj], P ∪ {(s0, j)} | (~q, P)∈Qn−1(s, a)∧~vj∈Vn−1(s0)∧s06@Qn−1(s, a)}(5.5) In this case, U,E=∅. •Case 2. When the reached state s0was already previously reached from state s through action a, the previous pairwise update defined by the set Nhas already been performed in some previous step corresponding to the first time that state s0was reached, thus now N=∅. For correctly updating Q(s, a), we have to distinguish those vector estimates inside V(s0)that have previously updated some vector of Q(s, a)from those which not: –Set Udeals with the first kind of vectors in Q(s, a), which are updated with their associated vectors in V(s0). The formula is entirely analogous to the one in the single objective case: 5.3. Pareto MORL for Design 125 Un−1(s, a) = {((1 −αn)~q +αn[~rn+γ ~vj], P)| (~q, P)∈Qn−1(s, a)∧(s0, j)∈P∧~vj∈Vn−1(s0)}(5.6) If any vector inside V(s0)has updated a vector in Q(s, a), then U=∅. –Set Edeals with the second kind of vectors, arising when a previously unknown vector appears in V(s0)(we call this an extra vector). These vectors have not been used to update any vector of Q(s, a). The expression s0@Qn−1(s, a)∧(s0, j)6@Qn−1(s, a)characterizes this situation: as this is not the first time s0is reached, s0@Qn−1(s, a), but as ~vjis new, (s0, j)6@Qn−1(s, a). In this case, we cannot make use of vectors estimates inside Qn−1(s, a)to determine the value of the new vector, because all of them have already been supported by some vector estimate inside previous instances of V(s0), different from the extra vector ~vj. So in this situation we have to set from scratch the value of the vector in the new pair that is being inserted into Qn−1(s, a). However, we can establish the new set of indices with the available information of the pairs inside Qn−1(s, a). Given an extra vector ~vj, we will insert a new vector estimate in Qn(s, a)for each vector estimate inside Qn−1(s, a), with the set of indices that arises of removing the pair of the form (s0, k)(whatever kis) from the set of indices of the vector estimate, and then adding the pair (s0, j): En−1(s, a) = {(αn[~rn+γ ~vj],(P\s0)∪ {(s0, j)})| ~vj∈Vn−1(s0)∧s0@Qn−1(s, a)∧(s0, j)6@Qn−1(s, a) ∧ ∃~q (~q, P)∈Qn−1(s, a)}(5.7) If there are no new vectors appearing inside V(s0), then E=∅. When a vector estimate that was present in previous instances of V(s0)(and thus there is an associated vector estimate inside Qn−1(s, a)) has been removed, it is because now it represents a dominated policy. In that situation, the vector estimate inside Qn−1(s, a)supported by the vector estimate removed from Vn−1(s0) is not inside Qn(s, a). Notice that PQ-learning keeps a vector in Q(s, a)for each possible combination of non-dominated vectors from the state-vector sets of reachable states. However, by 126 Chapter 5. Computational Techniques for Learning and Detecting Criteria in Design Problems application of Bellman’s optimality principle, only the subset of non-dominated state vectors of s,V(s), are needed to support action vectors in other Q sets. 5.3.1.3 Action Selection Mechanism As Q-learning, PQ-learning is an off-policy technique, meaning that the policy that is followed during learning is not the same as the one learned. Indeed, this fact is even more evident in the multi-objective setting, as we are learning several policies at once, but the agent is only following one path. This off-policy essence allows the agent to follow any policy during the learning process, as long as every state-action pair (s, a)is visited a potentially infinite number of times. Nevertheless, devising a proper action-selection strategy can lead to a better online performance. The usual intuition behind an action-selection strategy is that, when exploiting the already acquired knowledge, we choose one of the actions that yield a maximum value. In a scalar setting we only have one maximum value, and if there is a draw, then we choose one of the values randomly and take the action that yields it. The spirit of the mechanism presented here is similar, as we can consider that all the vector estimates inside V(s)are maximum values (because they are non-dominated). However, the chances of choosing a particular action are not equally distributed: the chances of choosing an action a, being in state s, are proportional to the number of vector estimates of Q(s, a)that are also inside V(s). Pr{an=a|sn=s}=|{~q :~q ∈Vn−1(s)∧ ∃P: (~q, P)∈Qn−1(s, a)}| |Vn−1(s)|(5.8) In our experiments we have used a -greedy mechanism, that is, with probability  a random action is chosen, and with (1 −)an action is chosen according to Expression 5.8. The balance between exploitation and exploration in this framework will be studied in Section 5.3.1.6. 5.3.1.4 Using the Learned Policies In scalar Q-learning, once the values have been learned, we can derive the optimal (or near-optimal) policy by choosing the action that yields the maximum value. That is, if we are in state s, the chosen action is argmaxaQ(s, a). However, in PQ-learning we cannot use this operator, since we do not have scalar values Q(s, a)any more, but sets Q(s, a). Moreover, our policies are non-stationary, so they do not condition only in the current state, but also in the current time step. 5.3. Pareto MORL for Design 127 As our algorithm has been devised to work without the foreknowledge of the preferences or weights for each objective, after the learning phase comes a selection phase, in which we can resort to a particular weight combination or just to a user selection process in which a single solution is directly chosen from the set. Regardless the selection method, the decision has to be made in the time step t0, that is, at the beginning of the process. The process for deriving a concrete learned policy in our case starts by computing the V-set of the initial state (see Expression 5.3). Once we have this V-set, we have to select a vector estimate out of it: ~qt0= Θ(V(s0)) (5.9) Where Θ() is a selection operator. The action to be taken in state s0and time step t0is the one whose associated Q-set contains the chosen vector estimate: π(s0, t0) = a: (∃Pt0: (~qt0, Pt0)∈Q(s0, a)) (5.10) In the following time steps the selection operator is no longer needed, because the decision of which policy is going to be followed has been already done. We must resort to the set of indices Passociated to the last chosen action, that is, Pt0. In time step t1, we need to look for the vector estimate inside V(s1)indexed in Pt0: ~qt1=~vi:~vi∈V(s1)∧(s1, i)∈Pt0(5.11) And the chosen action in state s1and time step t1is: π(s1, t1) = a: (∃Pt1: (~qt1, Pt1)∈Q(s1, a)) (5.12) It could happen that, when n > 0, we cannot find the suitable vector estimate ~qtn inside V(sn). This is a symptom that the learning process is not completed, and we still have a vector estimate inside V(s0)whose supporting values are no longer nondominated. In that case we can use the selection operator again in order to choose a vector estimate inside V(sn). Thus, in general, if we are in state snat time step tn, the action to take is given by the expression: 128 Chapter 5. Computational Techniques for Learning and Detecting Criteria in Design Problems π(sn, tn) = a: (∃Ptn: (~qtn, Ptn)∈Q(sn, a)) (5.13) Where ~qtn=       Θ(V(s0)) if n= 0 ~vi:~vi∈V(sn)∧(s, i)∈Ptn−1if n > 0∧ ∃~vi Θ(V(sn)) otherwise (5.14) 5.3.1.5 PQ-learning in Action Let us assume a state transition diagram for a multi-objective Markov decision process as depicted in figure 5.25. The task is episodic, it always start at state s1, and and terminates whenever the agent reaches any of the states s3,s4or s5(terminal states). Action a1has a probabilistic outcome and may lead to states s2or s3. Let us assume that for all terminal states s0we have V(s0) = {[~v1= (0,0),∅]}, i.e. each state has a single zero vector that is not supported by any index. Additionally, values for Qare not defined, since there are no available actions at terminal states. We will apply PQ-learning to this example assuming α= 0.1, and γ= 1. The evolution of Qand Vare displayed in table 5.16 for all state-action pairs and nonterminal states, and for each time step. The initial conditions are given for time step t= 0. What follows is a description of a possible sequence of transitions that illustrates the application of the PQ-learning rule. 1. A first episode starts at s1, where a1is the only action available. Let us assume the transition leads to s2with reward ~r = (0,0). Since V(s2)has two vectors, the application of the PQ-learning rule results in the following, N1(s1, a1) = {[(0.9×(0,0) + 0.1×((0,0) + (0,0)),{(s2,1)}] [(0.9×(0,0) + 0.1×((0,0) + (0,0)),{(s2,2)}]} U1(s1, a1) = ∅ E1(s1, a1) = ∅ Q1(s1, a1) = {[~v1= (0,0),{(s2,1)}] [~v2= (0,0),{(s2,2)}]} 2. Assume that at t= 2 action a2is chosen, leading to state s4with reward ~r = (1000,2000). Notice that after this step, V(s2)has only one non-dominated 5.3. Pareto MORL for Design 129 vector. N2(s2, a2) = {[(0.9×(0,0) + 0.1×((1000,2000) + (0,0)),{(s4,1)}]} U2(s2, a2) = ∅ E2(s2, a2) = ∅ Q2(s2, a2) = {[~v1= (100,200),{(s4,1)}]} 3. At t= 3 a new episode starts, transitioning again from s1to s2. Now, V(s2) = {[~v1= (100,200)(s4,1)]}, therefore, N3(s1, a1) = ∅ U3(s1, a1) = {[(0.9×(0,0) + 0.1×((0,0) + (100,200)),{(s2,1)}]} E3(s1, a1) = ∅ Q3(s1, a1) = {[~v1= (10,20),{(s2,1)}]} 4. Assume now that at t= 4 action a3is chosen, due to an exploration step. This leads to state s5with reward (2000,1000). Since this state is reached for the first time from state-action pair (s2, a3), the rule is applied as follows, N4(s2, a3) = {[(0.9×(0,0) + 0.1×((2000,1000) + (0,0)),{(s5,1)}]} U4(s2, a3) = ∅ E4(s2, a3) = ∅ Q4(s2, a3) = {[~v2= (200,100),{(s5,1)}]} 5. At t= 5 a third episode starts, transitioning once again stochastically from s1 to s2. However, now V(s2)presents an extra vector. Therefore, N5(s1, a1) = ∅ U5(s1, a1) = {[(0.9×(10,20) + 0.1×((0,0) + (100,200)),{(s2,1)}]} E5(s1, a1) = {[(0.1×((0,0) + (200,100)),{(s2,2)}]} Q5(s1, a1) = {[~v1= (19,38),{(s5,1)}] [~v3= (20,10),{(s2,2)}]} 130 Chapter 5. Computational Techniques for Learning and Detecting Criteria in Design Problems Figure 5.25: Sample state transition diagram. 6. Assume the episode terminates with a new transition from s2to s4. The update rule is applied as follows, N6(s2, a2) = ∅ U6(s2, a2) = {[(0.9×(100,200) + 0.1×((1000,2000) + (0,0)),{(s4,1)}]} E6(s2, a2) = ∅ Q6(s2, a2) = {[~v1= (190,380),{(s4,1)}]} 7. Finally, let us assume the last episode leads from s1to s3. This illustrates the case where each vector in Q(s1, a1)is supported by two vectors, one from s2, and other from s3, N7(s1, a1) = {[(0.9×(19,38) + 0.1×((1000,1000) + (0,0)),{(s2,1)(s3,1)}] [(0.9×(20,10) + 0.1×((1000,1000) + (0,0)),{(s2,2)(s3,1)}]} U7(s1, a1) = ∅ E7(s1, a1) = ∅ Q7(s1, a1) = {[~v1= (117.1,134.2),{(s2,1)(s3,1)}] [~v3= (118,109),{(s2,2)(s3,1)}]} 5.3. Pareto MORL for Design 131 t s (s, a)Qt(s, a)Vt(s) 0s1(s1, a1)~v1= (0,0) ∅~v1= (0,0) ∅ s2(s2, a2)~v1= (0,0) ∅~v1= (0,0) ∅ (s2, a3)~v2= (0,0) ∅~v2= (0,0) ∅ 1s1(s1, a1)~v1= (0,0) (s2,1) ~v1= (0,0) (s2,1) ~v2= (0,0) (s2,2) ~v2= (0,0) (s2,2) s2(s2, a2)~v1= (0,0) ∅~v1= (0,0) ∅ (s2, a3)~v2= (0,0) ∅~v2= (0,0) ∅ 2s1(s1, a1)~v1= (0,0) (s2,1) ~v1= (0,0) (s2,1) ~v2= (0,0) (s2,2) ~v2= (0,0) (s2,2) s2(s2, a2)~v1= (100,200) (s4,1) ~v1= (100,200) (s4,1) (s2, a3)~v2= (0,0) ∅ 3s1(s1, a1)~v1= (10,20) (s2,1) ~v1= (10,20) (s2,1) s2(s2, a2)~v1= (100,200) (s4,1) ~v1= (100,200) (s4,1) (s2, a3)~v2= (0,0) ∅ 4s1(s1, a1)~v1= (10,20) (s2,1) ~v1= (10,20) (s2,1) s2(s2, a2)~v1= (100,200) (s4,1) ~v1= (100,200) (s4,1) (s2, a3)~v2= (200,100) (s5,1) ~v2= (200,100) (s5,1) 5s1(s1, a1)~v1= (19,38) (s2,1) ~v1= (19,38) (s2,1) ~v3= (20,10) (s2,2) ~v3= (20,10) (s2,2) s2(s2, a2)~v1= (100,200) (s4,1) ~v1= (100,200) (s4,1) (s2, a3)~v2= (200,100) (s5,1) ~v2= (200,100) (s5,1) 6s1(s1, a1)~v1= (19,38) (s2,1) ~v1= (19,38) (s2,1) ~v3= (20,10) (s2,2) ~v3= (20,10) (s2,2) s2(s2, a2)~v1= (190,380) (s4,1) ~v1= (190,380) (s4,1) (s2, a3)~v2= (200,100) (s5,1) ~v2= (200,100) (s5,1) 7s1(s1, a1)~v1= (117.1,134.2) (s2,1)(s3,1) ~v1= (117.1,134.2) (s2,1)(s3,1) ~v3= (118,109) (s2,2)(s3,1) ~v3= (118,109) (s2,2)(s3,1) s2(s2, a2)~v1= (190,380) (s4,1) ~v1= (190,380) (s4,1) (s2, a3)~v2= (200,100) (s5,1) ~v2= (200,100) (s5,1) Table 5.16: Evolution of estimated values over time with PQ-learning. Thicker horizontal lines indicate division between training episodes. 132 Chapter 5. Computational Techniques for Learning and Detecting Criteria in Design Problems 5.3.1.6 Benchmark Results Now we analyse the results obtained when applying PQ-learning to two benchmark problems proposed by Vamplew et al. (2011). We have measured the train/test performance, suitable for multiple-policy algorithms, as they are likely to be used in an off-line setting (Vamplew et al., 2011). As several policies are learned at once, every time a set of policies is evaluated we compute the hypervolume of the set of accumulated vectorial rewards obtained by each intermediate learned policy (Vamplew et al., 2011). The hypervolume of a set of vectors S, given a reference point dominated by every vector in S, is the volume of the space that is dominated by the points in Sand that dominates the reference point. The quality of a set of learned policies is measured comparing its hypervolume with the hypervolume of the true front. All results in this section have been averaged over ten runs of the algorithm, on a Intel Core i7 CPU @2.80Ghz with 8 GB RAM and Windows 7. 5.3.1.6.1 Deep Sea Treasure. The first problem considered is Deep Sea Treasure (DST). This problem can be used to test if a MORL algorithm is able to find all the state vectors for a problem where these define a non-convex frontier in reward space (Vamplew et al. (2008)). DST has two objectives, and its true front of non-dominated solutions contains ten state vectors and has a hypervolume of 535, according to the reference point (−20,0). The environment is a grid of 10 rows and 11 columns, as we can see in Figure 5.26(a). The agent controls a submarine that searches for undersea treasures. There are ten treasure locations with different values; the first objective is to minimize the time that the submarine takes to reach the treasure, and the second one is to maximize the value of the achieved treasure. The task is episodic, with each episode starting in the top-left position of the grid and ending when a treasure is reached or after 1000 actions have been taken by the agent. At each step, four actions are available: moving one square to the top, right, bottom or left. If an action would move the submarine outside of the grid, then the position of the submarine remains unchanged. The reward received at each step is a vector of 2 elements; the first one is a punishment of −1for the time consumed, and the second one is the value of the achieved treasure, that will be 0in all steps except when the agent reaches a treasure location (the values are indicated in Figure 5.26(a)). In Figure 5.26(b) we can see the ten non-dominated accumulated rewards associated to the non-dominated policies of this problem. We need to set three parameters for PQ-learning: the discount rate, the learning rate and the exploration rate. In our experimentations we have found that the process