Computational Network Design from Functional Specifications

1ASU     2UCL     3KAUST     4Bath Univ.     5Urban Agency     6NLPR-CASIA


We propose an algorithm that generates networks for design scenarios like mid-scale urban street layouts (a-c) and floorplans for office spaces (d). The user simply specifies an input mesh as the problem domain along with high-level specifications of the functions of the generated network. Examples include preference for interior-to-boundary traffic (a) or interior-to-interior traffic (b), networks with specified destinations (i.e., sinks) on the boundary (c,d) and local feature control, such as reducing T-junctions (b) or forbidding dead-ends (c). For (a-c), the average travel time (distance) for interior-to-boundary traffic as estimated by the traffic simulator SUMO is indicated in green.


Connectivity and layout of underlying networks largely determine agent behavior and usage in many environments. For example, transportation networks determine the flow of traffic in a neighborhood, whereas building floorplans determine the flow of people in a workspace. Designing such networks from scratch is challenging as even local network changes can have large global effects. We investigate how to computationally create networks starting from only high-level functional specifications. Such specifications can be in the form of network density, travel time versus network length, traffic type, destination location, etc. We propose an integer programming-based approach that guarantees that the resultant networks are valid by fulfilling all the specified hard constraints and that they score favorably in terms of the objective function. We evaluate our algorithm in two different design settings, street layout and floorplans to demonstrate that diverse networks can emerge purely from high-level functional specifications.


Example results. Sink vertices are marked in red. The coverage range is two edges wide. The distance values of active half-edges are colored (see legends for color ranges). Boundary edges are excluded from the calculations. We forbid deadends and edges that are too close to each other. (a) to (c): A typical urban layout scenario such that all boundary vertices are sinks. The first two use different weights to optimize for (a) numbers of network edges and (b) sum of distance values. Note that we do not specifically constrain the maximum distance values. (c): A result that also optimizes for distance values but with the point-to-point constraint enabled (sampled vertices are marked in yellow). (d): We now constrain a boundary vertex (top middle) to be the sole sink. (e) to (g): A typical floorplan scenario such that a few inner vertices are sinks (e.g., elevators). Similarly, they differ by different relative weights and whether the point-to-point constraint is enabled.

Pipeline. For each sub-region, as determined by the input major roads, we generate layouts in three levels of decreasing coverage ranges. For each level, a rough street network is first generated by the IP-based approach (shown in gray). Afterwards, the geometry of the generated street network is refined by a smoothing process. Dead-ends are typically allowed only at the last level.

Optimization results with changing λL (to minimize network lengths) versus λD (to minimize travel distances). A larger λL leads to shorter network lengths but longer travel distances, while a larger λD leads to the opposite.

Diverse street layouts resulting from different functional specifications. The first two layouts are optimized for (a) minimal network lengths and (b) minimal travel distances to the boundary, using different specifications of the optimization weights. The travel distances are shown in the bottom-left corners. (c) A layout with a single exit on the left. We also prefer a tree-like structure for this case, which is realized by allowing deadends on the second (collector roads) level. (d) A layout that encourages through-traffic in the vertical direction. This is realized by enforcing a shortest path connecting the two user-specified vertices (green) without inner branches on the second level. Note that through-traffic in other directions (e.g., horizontal) is implicitly discouraged. (e) A network that better supports interior-to-interior traffic, realized by the point-to-point constraint with a user-specified partition.

Case study: Various scenarios created using functional specifications (see paper for details). L denotes the total street length in meters, d the average travel distance for specified traffic demand, and SUMO indicates the average travel distance per the SUMO traffic simulator. The color-coded street network shows the traffic distribution over different road segments (gray indicates no traffic).

Parcel and building layout using CityEngine based on street layout in (g) on the left. Note that since our algorithm ensures that the streets are appropriately spaced parcelling for the buildings remains a simple task without requiring any street modifications.

 title = {Computational Network Design from Functional Specifications},
 author = {Peng, Chi-Han and Yang, Yong-Liang and Bao, Fan and 
            Fink, Daniel and Yan, Dong-Ming and Wonka, Peter and Mitra, N. J.},
 journal = {ACM Transactions on Graphics (Proceedings of SIGGRAPH 2016)},
 volume = {35},
 issue = {4},
 pages = {},
 year = {2016},

We thank the reviewers for their comments and suggestions for improving the paper. Special thanks to Stephen Marshall and Benjamin Heydecker for sharing their knowledge, expertise, and experience regarding urban street network design and traffic planning, and to Carlos Molinero, Clmentine Cottineau and Elsa Arcaute for initial discussions. This work was supported in part by the ERC Starting Grant SmartGeometry (StG-2013-335373), Marie Curie CIG 303541, the National Science Foundation, Office of Sponsored Research (OSR) under Award No. OCRF-2014-CGR3-62140401, research funding from King Abdullah University of Science and Technology (KAUST), EPSRC Grant EP/K02339X/1 and EP/M023281/1, and National Natural Science Foundation of China (Nos. 61372168 and 61572502).


Paper (10.3 MB)

Presentation (13.4 MB)