The launch point of our conversation regarding the prototype which is focused on tracking people and things, hovered around the idea of “dynamic transportation networks”. An interesting and ambitious idea to say the least, but perhaps the idea is more solution than design tool. To open up the proposition and get at some of the fundamentals that might drive the components of such a solution toward design tools, lets abstract back from bus’s + people.
At the very least one would have to know about the following things:
- where groups of people were at and where they wanted to go
- the state of the network (roads) on which the buses operated
- where buses are within the network and what the state of those buses are
To generate dynamic routes for the buses would then involve an algorithm which could find and evaluate paths within the network. This is not unlike systems currently in use by emergency management services to dispatch people and resources for things such as building fires.
To continue the abstraction we could say that the three things we need to be able to do are
- identify properties of agents which occupy the network in continuous and discontinuous ways. What or who is at or near a particular node or edge within the network and what properties are exposed to them.
- manage the nodes and edges of the network, what are their properties? how do we logically traverse the edges of the network?
- formulate singular paths or sub networks from within the network. Consider the way in which a single path through a collection of network nodes, is itself a network, if only a simple one
In this way, the underlying mechanisms that enable us to find say the fastest, or shortest route for a bus might be the same mechanisms that we would use to form ad-hoc networks through nearly any system which can be considered as a network. Perhaps the prototyped design tool might allow it’s user to generate or identify particular sub networks which a person or thing is connected to based on where they are at in space? Of course one of the more interesting conditions of this type of network thinking, still has to do with our “position” or “location” in a network, but perhaps those networks might be logical networks but not physical networks. For instance, where are you located with respect to the social or professional network that is the Architecture community of Chicago, or of the world. Through forming, collecting and analyzing these sub networks over time perhaps we can begin to understand not only where we are or what we are connected to, but how the super networks might be better organized. What kinds of feedback loops can be established here?
Ultimately this question of “Where Is Something”, physically, logically, semantically, is at the heart of what will see in the emerging paradigm of contextual computing.
The graph, a term for network from the area of mathematics referred to as graph theory, describes a collection of nodes and the edges which connect them. Graph theory is one of the most critical and fundamental aspects to computation and data. Much of the underlying data structures for modern software rely on graph representations of system components. Learning how to logically or computationally move or traverse through graphs is essential to searching, sorting, analyzing, and generating: algorithm’s such as Depth-first search, Breadth-first search, Dijkstra’s algorithm, Nearest neighbour algorithm. More specifically algorithm’s such as A* pathfinding algorithms, which underpin much of the artificial intelligence world from video games to data mining, enable goal or objective based navigation of complex networks.
Networks in Databases
To get started operating on data networks it is imperative that we properly store our networked data. While we will likely not be utilizing explicitly graph oriented databases, it is worth mentioning that databases organized around the premise of graph’s exist. In the studio and seminar we will be focusing on the utilization of the postgres/postgis relational database. Fortunately the prevalence of networks in geospatial thinking has lead to the development of some critical tools which aid in our analysis of networks using postgis data structures.
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
Advantages of the database routing approach are:
- Data and attributes can be modified by many clients, like Quantum GIS and uDigthrough JDBC, ODBC, or directly using Pl/pgSQL. The clients can either be PCs or mobile devices.
- Data changes can be reflected instantaneously through the routing engine. There is no need for precalculation.
- The “cost” parameter can be dynamically calculated through SQL and its value can come from multiple fields or tables.
In addition a series of tools for importing data such as street networks have been developed for pgRouting enabling aquisition from sources such as Open Street Map; OSM2PGSQL, and OSM2PGROUTING
Tutorials: beginners guide, workshop (extensive)
Startup technologies (first prototype)
Without presuming too much about the prototype, it’s safe to say that the system would take some kind of input (perhaps from the physical world i.e. sensor or maybe through an interactive interface), analysis or computation would be performed and some type of network oriented output produced.
Because of the immediacy to topics of transportation and logistics which spear headed the project, I would suggest that you simply begin with the transportation network data which we have access to through the data portal and OSM. A first pass tech prototype would therefore include:
- the process of importing this data into pgRouting friendly structures
- demonstrable querying and route formation using pgRouting SQL queries
- the representation of generated routes within qgis or google earth.
- Additional considerations might include the integration of CTA api data into our database. This would involve a simple app which could parse the XML data from the CTA’s system into table structures in our PostGres db for inclusion with base network data.
From this point, we can validate functionality and begin to think more laterally about the criteria used to create and/or interact with the data. We start with shape based networks (road center lines), developing an understanding of how pgRouting is working, then begin to explore other networks and forming networks on the fly rather than as shape file imports.
- Graph Theory
- Koenigsberg Bridge Problem
- Dijkstra’s Algorithm
- A* Pathfiinding algorithms
- CTA Transportation API
- XML to PGSQL
- OSM2PGROUTING, OSM2PGSQL
- Internet of Things
- iBeacon, NFC, BlueToothLE
- Mesh networking