Computational network design from functional specifications

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.

References

1. AlHalawani, S., and Mitra, N. J. 2015. Advances in Visual Computing: ISVC 2015, Part II. ch. Congestion-Aware Warehouse Flow Analysis and Optimization, 702--711.
2. AlHalawani, S., Yang, Y.-L., Liu, H., and Mitra, N. J. 2013. Interactive facades: Analysis and synthesis of semi-regular facades. Computer Graphics Forum (Proc. EUROGRAPHICS) 32, 2pt2, 215--224.
3. AlHalawani, S., Yang, Y.-L., Wonka, P., and Mitra, N. J. 2014. What makes London work like London. Computer Graphics Forum (Proc. SGP) 33.
4. Aliaga, D., Vanegas, C., and Benes, B. 2008. Interactive Example-Based Urban Layout Synthesis. ACM TOG (Siggraph Asia) 27, 5.
5. Bao, F., Yan, D.-M., Mitra, N. J., and Wonka, P. 2013. Generating and exploring good building layouts. ACM TOG (Siggraph) 32, 4.
6. Baswana, S., and Sen, S. 2007. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms 30, 4, 532--563.
7. Board, T. R. 2010. Highway Capacity Manual. Transportation Research Board.
8. Chen, G., Esch, G., Wonka, P., Müller, P., and Zhang, E. 2008. Interactive procedural street modeling. ACM TOG (Siggraph) 27, 3, 103:1--9.
9. Deussen, O., Hanrahan, P., Lintermann, B., Měch, R., Pharr, M., and Prusinkiewicz, P. 1998. Realistic modeling and rendering of plant ecosystems. In Proc. ACM SIGGRAPH, 275--286.
10. Galin, E., Peytavie, A., Guérin, E., and Benes, B. 2011. Authoring hierarchical road networks. Computer Graphics Forum 29, 7, 2021--2030.
11. Garcia-Dorado, I., Aliaga, D. G., and Ukkusuri, S. V. 2014. Designing large-scale interactive traffic animations for urban modeling. Computer Graphics Forum (Proc. EUROGRAPHICS) 33, 2, 411--420.
12. Génevaux, J.-D., Galin, E., Guérin, E., Peytavie, A., and Beneš, B. 2013. Terrain generation using procedural models based on hydrology. ACM TOG (Siggraph) 32, 4, 143:1--143:13.
13. Gurobi Optimization, Inc., 2014. Gurobi optimizer reference manual.
14. Handy, S., Paterson, R., and Butler, K. 2003. Planning for street connectivity: Getting from here to there. In Planning Advisory Service Report.
15. Kass, M., Witkin, A., and Terzopoulos, D. 1988. Snakes: Active contour models. Int. Journal of Computer Vision 1, 4, 321--331.
16. Koster, A., Kutschka, M., and Raack, C. 2010. Towards robust network design using integer linear programming techniques. In Next Generation Internet (NGI), 2010 6th EURO-NF Conference on, 1--8.
17. Krajzewicz, D., Erdmann, J., Behrisch, M., and Bieker, L. 2012. Recent development and applications of SUMO - Simulation of Urban MObility. International Journal On Advances in Systems and Measurements 5, 3&4, 128--138.
18. Liu, H., Yang, Y.-L., AlHalawani, S., and Mitra, N. J. 2013. Constraint-aware interior layout exploration for precast concrete-based buildings. The Visual Computer (CGI Special Issue).
19. Luathep, P., Sumalee, A., Lam, W. H., Li, Z.-C., and Lo, H. K. 2011. Global optimization method for mixed transportation network design problem: A mixed-integer linear programming approach. Transportation Research Part B: Methodological 45, 5, 808--827.
20. Ma, C., Vining, N., Lefebvre, S., and Sheffer, A. 2014. Game level layout from design specification. Computer Graphics Forum (Proc. EUROGRAPHICS) 33, 2, 95--104.
21. Maréchal, N., Guérin, E., Galin, E., Merillou, S., and Mrillou, N. 2010. Procedural generation of roads. Computer Graphics Forum 29, 2, 429--438.
22. Marshall, S. 2005. Streets & Pattern. Spon press, New York.
23. MATSim, 2015. Matsim, http://www.matsim.org/.
24. Merrell, P., Schkufza, E., and Koltun, V. 2010. Computer-generated residential building layouts. ACM TOG (Siggraph Asia) 29, 6, 181:1--181:12.
25. Meyer, M., and Miller, E. 2000. Urban Transportation Planning. McGraw-Hill.
26. Miller, C. E., Tucker, A. W., and Zemlin, R. A. 1960. Integer programming formulation of traveling salesman problems. J. ACM 7, 4, 326--329.
27. Nishida, G., Garcia-Dorado, I., and Aliaga, D. G. 2015. Example-driven procedural urban roads. Computer Graphics Forum, 1--14.
28. Ortzar, J. d. D., and Willumsen, L. 2011. Modelling Transport. Wiley.
29. Parish, Y. I. H., and Müller, P. 2001. Procedural modeling of cities. In Proc. ACM SIGGRAPH, 301--308.
30. Peng, C.-H., Barton, M., Jiang, C., and Wonka, P. 2014. Exploring quadrangulations. ACM TOG 33, 1, 12:1--12:13.
31. Peng, C.-H., Yang, Y.-L., and Wonka, P. 2014. Computing layouts with deformable templates. ACM TOG (Siggraph) 33, 4, 99:1--99:11.
32. Runions, A., Fuhrer, M., Lane, B., Federl, P., Rolland-Lagan, A.-G., and Prusinkiewicz, P. 2005. Modeling and visualization of leaf venation patterns. ACM TOG (Siggraph) 24, 3, 702--711.
33. Sewall, J., Wilkie, D., Merrell, P., and Lin, M. 2010. Continuum Traffic Simulation. Computer Graphics Forum (Proc. EUROGRAPHICS) 29, 2, 439--448.
34. Sewall, J., Wilkie, D., and Lin, M. C. 2011. Interactive hybrid simulation of large-scale traffic. ACM TOG (Siggraph Asia) 30, 6.
35. Southworth, M., and Ben-Joseph, E. 2003. Streets and the Shaping of Towns and Cities. Island Press, Wasington DC.
36. Vanegas, C. A., Aliaga, D. G., Beneš, B., and Waddell, P. A. 2009. Interactive design of urban spaces using geometrical and behavioral modeling. ACM TOG (Siggraph Asia) 28, 5.
37. Vanegas, C. A., Garcia-Dorado, I., Aliaga, D. G., Benes, B., and Waddell, P. 2012. Inverse design of urban procedural models. ACM TOG (Siggraph Asia) 31, 6, 168:1--168:11.
38. VISSIM, 2015. http://vision-traffic.ptvgroup.com/.
39. Wardrop, J. 1952. Some theoretical aspects of road traffic research. Proceedings of the Institution of Civil Engineers 1, 2, 325--378.
40. Weber, B., Müller, P., Wonka, P., and Gross, M. H. 2009. Interactive geometric simulation of 4D cities. Computer Graphics Forum (Proc. EUROGRAPHICS) 28, 2, 481--492.
41. Wilkie, D., Sewall, J., and Lin, M. C. 2013. Flow reconstruction for data-driven traffic animation. ACM TOG (Siggraph) 32, 4.
42. Yang, H., and Bell, M. 1998. Models and algorithms for road network design: a review and some new developments. Transport Reviews 18, 3.
43. Yang, Y.-L., Wang, J., Vouga, E., and Wonka, P. 2013. Urban pattern: Layout design by hierarchical domain splitting. ACM TOG (Siggraph Asia).
44. Yu, L.-F., Yeung, S.-K., Tang, C.-K., Terzopoulos, D., Chan, T. F., and Osher, S. 2011. Make it home: Automatic optimization of furniture arrangement. ACM TOG (Siggraph) 30, 4, 86:1--86:11.

Index Terms

• Computing methodologies

  • Computer graphics

    • Shape modeling

      • Shape analysis