Computational network design from functional specifications
Authors:
- Yong-Liang YangYYYong-Liang Yang
- Fan BaoFBFan Bao
- Dong-Ming YanDYDong-Ming Yan
- Niloy J. MitraNMNiloy J. Mitra
Open Access
- 11 July 2016
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 35 (4) , 1-12
Abstract
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.Keywords
All Related Versions
Funding Information
- National Natural Science Foundation of China (61372168, 61572502)
- EPSRC (EP/K02339X/1, EP/M023281/1)
- King Abdullah University of Science and Technology
This publication has 33 references indexed in Scilit:
- Make it homeACM Transactions on Graphics, 2011
- Computer-generated residential building layoutsACM Transactions on Graphics, 2010
- Interactive design of urban spaces using geometrical and behavioral modelingACM Transactions on Graphics, 2009
- Interactive Geometric Simulation of 4D CitiesComputer Graphics Forum, 2009
- Interactive example-based urban layout synthesisACM Transactions on Graphics, 2008
- Interactive procedural street modelingACM Transactions on Graphics, 2008
- Modeling and visualization of leaf venation patternsACM Transactions on Graphics, 2005
- Models and algorithms for road network design: a review and some new developmentsTransport Reviews, 1998
- Integer Programming Formulation of Traveling Salesman ProblemsJournal of the ACM, 1960
- ROAD PAPER. SOME THEORETICAL ASPECTS OF ROAD TRAFFIC RESEARCH.Proceedings of the Institution of Civil Engineers, 1952