Search

Motivated by reflection-in-action in architectural design, this article introduces a spatial synthesis artifact that relies on multi-agent reinforcement learning to address spatial goals with fine-grained control in a simulation. It relies on parameter sharing with proximal policy optimization and a parameterized reward function to train robust agent policies in random environments with random spatial problems. The agents are evaluated in three design cases: a house design with 12 agents in three sites, a museum with 18 agents in an interstitial urban site, and a speculative design of a housing complex with 96 agents on a large empty site. The policies performed well in all the cases and produced morphologically consistent solutions. However, in cases with a larger number of agents, the system largely benefited from a spring layout algorithm for the initialization. Future research will address more complex spatial synthesis problems and mechanisms for human-computer interaction. • The work formulates spatial synthesis as a multi-agent simulation with which human designers can interact with. • The method supports real-time and fine-granular interaction between designers and computational agents in a shared task. • The method uses parameter sharing, proximal policy optimization, and parameterized rewards to learn heterogeneous behaviors. • Policies trained on random environments produced consistent architectural configurations in different design cases. [ABSTRACT FROM AUTHOR]

Abstract Shapes are considered as finite arrangements of spatial elements from among points, line and plane segments, circles and ellipses, (circular) arcs, quadratic Bezier curves, of limited but non-zero measure, in 2D and 3D. Augmented shapes are defined as shapes augmented with attributes, e.g., labels, weights, colors, enumerative values, and (parametric) descriptions. Different attribute types specify different behaviors under operations of sum, product and difference and a part relationship. We review different shape–attribute propositions from the shape grammar literature and characterize them uniformly. This uniform characterization of augmented shapes is intended to assist in formalizing new shape–attribute propositions that may have been visually conceived. Highlights • A uniform characterization of different shape-attribute propositions is presented. • A uniform description of the behavior of shapes with attributes is proposed. • Characterizations of attribute types and spatial element types are almost uniform. [ABSTRACT FROM AUTHOR]

Previously, we examined tractable parametric shape grammars and developed a general paradigm for implementing classes of such grammars. A tractable shape grammar has polynomial computing complexity, and is specified in a way that is readily transformable to a computer program. By contrast, traditionally, shape grammars have been typically developed without a computer implementation in mind, either requiring ambiguity to be clarified, or it is hardly possible for the grammar to be implemented by a polynomial algorithm. Each tractable shape grammar is tied to a particular framework, which is backed by a data structure and supports a metalanguage. In this paper we illustrate the development of tractable shape grammars by transforming a shape grammar developed, essentially, in traditional fashion for the Baltimore rowhouse. The development is for a specific application context— to determine the interior layout of a building given its external features—and the process serves as a general strategy for developing tractable shape grammars. [ABSTRACT FROM AUTHOR]

Shape grammars are, in general, intractable. Even amongst tractable shape grammars, their characteristics vary significantly. This paper describes a paradigm for practical general shape grammar interpreters, which aim to address computational difficulties posed by parameterization. The paradigm is expressed in terms of frameworks each comprising an underlying data structure, manipulation algorithms, and a metalanguage. The approach is illustrated through three exemplar frameworks. [ABSTRACT FROM AUTHOR]

In this paper we explore the theoretical basis for a concept of 'computation-friendly' shape grammars, through a formal examination of tractability of the grammar formalism. Although a variety of shape grammar definitions have evolved over time, it is possible to unify these to be backwards compatible. Under this unified definition, a shape grammar can be constructed to simulate any Turing machine from which it follows that: a shape grammar may not halt; its language space can be exponentially large; and in general, its membership problem is unsolvable. Moreover, parametric subshape recognition is shown to be NP. This implies that it is unlikely, in general, to find a polynomial-time algorithm to interpret parametric shape grammars, and that more pragmatic approaches need to be sought. Factors that influence the tractability of shape grammars are identified and discussed. [ABSTRACT FROM AUTHOR]

An algorithm is described for determining the interior layout of a building given three pieces of information: (1) the footprint of each story; (2) a reasonably complete set of exterior features; and (3) a shape grammar that describes the building style. Essentially, the algorithm prunes a layout tree generated by interpreting the shape grammar with constraints extracted from the footprint and exterior features. The Queen Anne house, commonly located in Pittsburgh, is chosen as the exemplars of the building style. It is shown how a shape-grammar interpreter for the Queen Anne house was developed and applied to the preceding problem. This shape-grammar interpreter provides the basis for developing grammar interpreters for general parametric shapes. For the purposes of illustration and comparison, applications of the approach to two other distinct building styles are briefly described. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a generalized version of the Watchman Route Problem (WRP) where the objective is to plan a continuous closed route in a polygon (possibly with holes) and a set of discrete viewpoints on the planned route such that every point on the polygon boundary is visible from at least one viewpoint. Each planned viewpoint has some associated cost. The total cost to minimize is a weighted sum of the view cost, proportional to the number of viewpoints, and the travel cost, the total length of the route. We call this problem the Generalized Watchman Route Problem or the GWRP. We tackle a restricted nontrivial (it remains NP-hard and log-inapproximable) version of GWRP where each polygon edge is entirely visible from at least one planned viewpoint. We call it Whole Edge Covering GWRP. The algorithm we propose first constructs a graph that connects O(n12) number of sample viewpoints in the polygon, where n is the number of polygon vertices; and then solves the corresponding View Planning Problem with Combined View and Traveling Cost, using an LP-relaxation based algorithm we introduced in [27, 29]. We show that our algorithm has an approximation ratio in the order of either the view frequency, defined as the maximum number of sample viewpoints that cover a polygon edge, or a polynomial of log n, whichever is smaller. [ABSTRACT FROM AUTHOR]

We consider a capacitated max k-cut problem in which a set of vertices is partitioned into k subsets. Each edge has a non-negative weight, and each subset has a possibly different capacity that imposes an upper bound on its size. The objective is to find a partition that maximizes the sum of edge weights across all pairs of vertices that lie in different subsets. We describe a local-search algorithm that obtains a solution with value no smaller than 1 − 1/ k of the optimal solution value. This improves a previous bound of 1/2 for the max k-cut problem with fixed, though possibly different, sizes of subsets. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we examine the problem of determining the self-duality of a monotone boolean function in disjunctive normal form (DNF). We show that the self-duality of monotone boolean functions with n disjuncts such that each disjunct has at most k literals can be determined in time. This implies an algorithm for determining the self-duality of -DNF functions. We also consider the version where any two disjuncts have at most c literals in common. For this case we give an algorithm for determining self-duality. [Copyright &y& Elsevier]

We present a formal approach to representational flexibility, , to support alternative representations of an entity. The approach is constructive, based on a part relation on elements within a , which enables the recognition of emergent information. The use of data functions as a provides for the embedding of data queries within a representational structure. We discuss the application of to supporting alternative data views, illustrating this through a case study in building construction. [ABSTRACT FROM AUTHOR]

Abstract: The objective of this study was to distinguish within a population of patients with and without breast cancer. The study was based on the University of Wisconsin''s dataset of 569 patients, of whom 212 were subsequently found to have breast cancer. A subset-conjunctive model, which is related to Logical Analysis of Data, is described to distinguish between the two groups of patients based on the results of a non-invasive procedure called Fine Needle Aspiration, which is often used by physicians before deciding on the need for a biopsy. We formulate the problem of inferring subset-conjunctive rules as a 0–1 integer program, show that it is NP-Hard, and prove that it admits no polynomial-time constant-ratio approximation algorithm. We examine the performance of a randomized algorithm, and of randomization using LP rounding. In both cases, the expected performance ratio is arbitrarily bad. We use a deterministic greedy algorithm to identify a Pareto-efficient set of subset-conjunctive rules; describe how the rules change with a re-weighting of the type-I and type-II errors; how the best rule changes with the subset size; and how much of a tradeoff is required between the two types of error as one selects a more stringent or more lax classification rule. An important aspect of the analysis is that we find a sequence of closely related efficient rules, which can be readily used in a clinical setting because they are simple and have the same structure as the rules currently used in clinical diagnosis. [Copyright &y& Elsevier]

The dynamic Pickup and Delivery Problem with Time Windows (PDPTW) is faced by courier companies serving same-day pickup and delivery requests for the transport of letters and small parcels. This article focuses on the dynamic PDPTW for which future requests are not stochastically modelled or predicted. The standard solution methodology for the dynamic PDPTW is the use of a rolling time horizon as proposed by Psaraftis. When assigning a new request to a vehicle it may be preferable to consider the impact of a decision both on a short-term and on a long-term horizon. In particular, better managing slack time in the distant future may help reduce routing cost. This paper describes double-horizon based heuristics for the dynamic PDPTW. Computational results show the advantage of using a double-horizon in conjunction with insertion and improvement heuristics. [Copyright &y& Elsevier]

Vehicle routing problems involve the navigation of one or more vehicles through a network of locations. Locations have associated handling times as well as time windows during which they are active. The arcs connecting locations have time costs associated with them. In this paper, we consider two different problems in single vehicle routing. The first is to find least time cost routes between all pairs of nodes in a network for navigating vehicles; we call this the all pairs routing problem. We show that there is an O(log[sup 3] n) time parallel algorithm using a polynomial number of processors for this problem on a CREW PRAM. We next consider the problem in which a vehicle services all locations in a network. Here, locations can be passed through at any time but only serviced during their time window. The general problem is [formula] -complete under even fairly stringent restrictions but polynomial algorithms have been developed for some special cases. In particular, when the network is a line, there is no time cost in servicing a location, and all time windows are unbounded at either their lower or upper end, O(n[sup 2]) algorithms have been developed. We show that under the same conditions, we can reduce this problem to the all pairs routing problem and therefore obtain an O(log[sup 3] n) time parallel algorithm on a CREW PRAM. [ABSTRACT FROM AUTHOR]

A correction to the article "The Capacitated Max k-cut Problem" is presented.

We characterize the optimal solution to the linear programming relaxation of the standard formulation for the minimum satisfiability problem. We give a O (n m 2) combinatorial algorithm to solve the fractional version of the minimum satisfiability problem optimally where n (m) is the number of variables (clauses). As a by-product, we obtain a 2 (1 − 1 / 2 k) approximation algorithm for the minimum satisfiability problem where k is the maximum number of literals in any clause. [ABSTRACT FROM AUTHOR]

Given an edge-weighted graph the problem is to partition the vertices of the graph into k partitions of prescribed sizes such that the total weight of the edges within partitions are maximized. This problem is NP-complete for all k ≥ 2. We give a factor approximation where d is the ratio of the largest size and the smallest size in the partition. When the number of partitions k is 2, we give an approximation algorithm with performance ratio . [ABSTRACT FROM PUBLISHER]

In this paper, we consider the problem where a point robot in a 2D or 3D environment equipped with an omnidirectional range sensor of finite range D is asked to cover a set of surface patches, while minimizing the sum of view cost, proportional to the number of viewpoints planned, and the travel cost, proportional to the length of path traveled. We call it the Metric View Planning Problem with Traveling Cost and Visibility Range or Metric TVPP in short. We present a complexity result for the problem, i.e., we show that the Metric TVPP cannot be approximated within O(\log m) ratio by any polynomial algorithm, where m is the number of surface patches to cover. We then analyze a variant of an existing decoupled two-level algorithm of first solving the view planning problem to get an approximate solution, and then solving, again using an approximation algorithm, the Metric traveling salesman problem to connect the planned viewpoints. We then present performance bounds for this two-level decoupled algorithm, i.e., we show that it has an approximation ratio of O(\log m). Thus, it asymptotically achieves the best approximation ratio one can hope for. [ABSTRACT FROM PUBLISHER]

We provide constant ratio approximation algorithms for two NP-hard problems, the rectangle stabbing problem and the rectilinear partitioning problem. In the rectangle stabbing problem, we are given a set of rectangles in two-dimensional space, with the objective of stabbing all rectangles with the minimum number of lines parallel to the x and y axes. We provide a 2-approximation algorithm, while the best known approximation ratio for this problem is O(logn). This algorithm is then extended to a 4-approximation algorithm for the rectilinear partitioning problem, which, given an mx × my array of nonnegative integers and positive integers v, h, asks to find a set of v vertical and h horizontal lines such that the maximum load of a subrectangle (i.e., the sum of the numbers in it) is minimized. The best known approximation ratio for this problem is 27. Our approximation ratio 4 is close to the best possible, as it is known to be NP-hard to approximate within any factor less than 2. The results are then extended to the d-dimensional space for d ≥ 2, where a d-approximation algorithm for the stabbing problem and a dd-approximation algorithm for the partitioning problem are developed. [Copyright &y& Elsevier]

We consider the ( n − 2 , n ) cyclical scheduling problem which assigns a shift of n − 2 consecutive periods among a total of n periods to workers. We solve this problem by solving a series of b -matching problems on a cycle of n vertices. Each vertex has a capacity, and edges have costs associated with them. The objective is to maximize the total cost of the matching. The best known algorithm for this problem uses network flow, which runs in O ( n 2 log ⁡ n ) on a cycle. We provide an O ( n log ⁡ n ) algorithm for this problem. Using this, we provide an O ( n log ⁡ n log ⁡ n b max ) algorithm for the ( n − 2 , n ) cyclical scheduling problem, where b max is the maximum capacity on a vertex. [ABSTRACT FROM AUTHOR]

This paper discusses the integration of knowledge bases and shape grammars for the generation of building models, covering interaction, system, and implementation. Knowledge-based and generative systems are combined to construct a method for characterizing existing buildings, in particular, their interior layouts based on exterior features and certain other parameters such as location and real dimensions. The knowledge-based model contains information about spatial use, organization, elements, and contextual information, with the shape grammar principally containing style rules. Buildings are analyzed and layouts are generated through communication and interaction between these two systems. The benefit of using an interactive system is that the complementary properties of the two schemes are employed to strengthen the overall process. Ontologies capture knowledge relating to architectural design principles, building anatomy, structure, and systems. Shape grammar rules embody change through geometric manipulation and transformation. Existing buildings are analyzed using this approach, and three-dimensional models are automatically generated. Two particular building types, the vernacular rowhouse and high-rise apartment building, both from Baltimore, Maryland, are presented to illustrate the process and for comparing the utilized methodologies. [ABSTRACT FROM AUTHOR]

This paper may be viewed as a corrigendum as well as an extension of the paper by (Czumaj et al., Theoret. Comput. Sci. 262 (1–2), (2001) 569–582) where they deal with the variable length scheduling problem (VLSP) with parameters k1,k2, denoted VLSP(k1,k2). In the current paper, we first discuss an error in the analysis of one of the approximation algorithms described in (Czumaj et al., Theoret. Comput. Sci. 262 (1–2), (2001) 569–582), where an approximation algorithm for VLSP(k1,k2), k1, was presented and it was claimed that the algorithm achieves the approximation ratio of 1+(k1(k2−k1))/k2. In this paper we give a problem instance for which the same algorithm obtains the approximation ratio ≈k2/k1. We then present two simple approximation algorithms, one for the case k1 = 1 with an approximation ratio of 2, and one for the case k1>1 with an approximation ratio of 2+(k2/2k1). This corrects the result claimed in (Czumaj et al., Theoret. Comput. Sci. 262 (1–2), (2001) 569–582). [Copyright &y& Elsevier]