Street dirt and pedestrian traffic simulation
With the arrival of spring and rain on the street, one problem is becoming increasingly common. This one:
I think familiar to all the inhabitants of our cities. Eternally trampled lawns turning into a mud swamp after each rain, through which pedestrians selflessly continue to make their way. Pachkaya while clothing and carrying mud porridge on the pavement.
')
It is obvious that people here are generally not to blame, such is our nature - to always look for the shortest path. And it would be nice if the layout of public areas to meet this aspiration. But this, alas, is not so, and architects and planners with perseverance continue to draw paths and sidewalks along a ruler and with intersections at right angles, and pedestrians cut those corners wherever possible by trampling grass and spreading dirt.
Somehow I walked along the track and sluggishly pondered about the fact that once again I would have to either go around or get my shoes dirty. From a disturbance like “that's what fools design it for,” the thought flowed smoothly onto a bike heard about a certain science city, where the paths in the courtyards were not done at first, and then they simply asphalted people’s footpaths that were convenient for people. And from there, thought migrated to the idea of "why not do the same thing, but on the computer?". Develop a program that, according to a given map, will predict where people will trample lawns and where it would be nice to make asphalt pavement?
Under the cut - a description of the algorithm and a couple of examples of its work for real St. Petersburg courtyards.
To begin with, we will look at how local authorities responsible for landscaping deal with the problem of walking on lawns.
Option One: put fences
In most cases, an inefficient way. The fence will be broken sooner or later. In the photo below it was broken and hung back many times already, throwing out money for nothing.
Option Two: admit error and correct
Yes, it also happens. In this regard, I like the courtyards around Moskovsky Prospekt — the paths there have been turned into normal paths, and no one walks the lawns anymore — there is simply no need for that. However, it all depends on the enthusiasm of local authorities - someone does, someone writes formal replies, promises to make it in 5 years when there will be money, and most often they are trying to fight according to the first method.
Well, option three: to foresee and correct problems at the design stage.
Honestly, I have no idea what designers and developers are doing for this. Judging by the schemes I have seen - nothing, they mold everything based solely on aesthetic considerations. I would be happy if someone with experience in this field can say something in the comments.
This option we will do.
Formulation of the problem
So what do we have? And we have a map of the area on which there are:
It is necessary to predict exactly where pedestrians will walk on the lawns, so that on the basis of this it could be decided to create normal roads on the site.
We immediately note two boundary cases that usually come to mind first as a solution. The first one is a complete graph, that is, we simply take and connect each generator with each one, building roads in a straight line. In words, simply, pedestrians will, of course, be comfortable, but in the end the whole yard will be rolled up into the asphalt, which is expensive and unaesthetic. The second case is the minimum spanning tree of the graph, the peaks in which will be the generators. Unfortunately, people are still not robots and do not walk on minimal spanning trees, which was shown by researchers to work "Modeling the Evolution of Human Trail Systems" (D. Helbing, J. Keltsch, P. Molnar.) The illustration to this statement can Serve the following image:
The system of full paths is shown on the left, and the system of paths between the points indicated as a result of experiments from the above-mentioned work is shown on the right. It can be seen that it is neither complete nor spanning tree.
As a result of some thoughts and study of articles on the simulation of pedestrian traffic, the following algorithm was invented and implemented.
Algorithm
Training.
The map of the considered area of the territory is presented in the GeoJSON format. On it are manually marked pedestrian generators and cross-sections of the landscape.
Initialization. Based on the map, the navigation graph G (V, E) is constructed. The vertices of the graph V are the set of points of the terrain. In this paper, the simplest method for constructing this set is chosen: a rectangular grid is superimposed on the map, its nodes become the vertices of the graph. If a person can pass between two adjacent grid nodes, such nodes are connected by edges that make up the set E. The initial weight of each edge e is represented as the difference of two components: a fixed Wconst (e) , determined by the type of terrain, and a variable Wvar (e) , which will be called later extrudedness. Initially, it is zero. Some types of terrain (hard surface tracks) may not have a variable component.
Trampling is limited to zero (untouched lawn) from below, and from above, Wmax , selected so that even the most trampled path still is a little less attractive than a similar track.
In addition, for each pedestrian p, the coefficient of decency k (p) is introduced. This coefficient is used to simulate various categories of pedestrians - both “decent”, who always prefer to walk only along the paths, even if the final distance is much larger, and those who like to walk are always straight. The formula for calculating the weight W (e, p) of the edge e for a pedestrian p is:
In this case, if the value of k (p)> 1, the short straightened paths for this pedestrian will be more attractive, since the role of the Wvar component in the formula will be higher. When k <1, you get a “decent” pedestrian who will try to walk along the paths more often.
Simulation.
P pedestrians are evenly distributed on the generators. Goals for them are selected randomly from the list of other generators. The coefficient of decency k (p) is selected as follows:
Here Kbad is an obligatory share of dishonest pedestrians (to speed up the convergence of the algorithm, we assume that there is always a certain proportion of people in the community who want to move in the most direct and short ways), N is the normal distribution. The values of the coefficients are chosen empirically, the value 0.1 is selected for Kbad .
At each step of the simulation, the following actions are performed:
1) pedestrians walk a certain distance depending on a given speed of movement;
2) trampling by the pedestrians of the graph edges increases by a fixed value of ∆Wped for each pedestrian passing through them;
3) pedestrians that have reached their goal are replaced with new ones;
4) trampling of all edges of the graph is reduced by a fixed value ∆Wtime (overgrowing with time).
Thus, the total change in trampling for the edge e after the simulation step i looks like:
Here Pcount (e, i) is the number of pedestrians who passed at the i step along the edge e .
Pedestrians pave a route using the heuristic algorithm A * c to straighten the paths (initially I used the banal Dijkstra, but on rectangular grids he likes to generate rather unnatural-looking paths). The simulation continues either until convergence, until the map of paths stops changing, or a specified number of steps. After the completion of the simulation, the map with the distribution of trampling demonstrates the areas where pedestrians most often go off the tracks to the ground, and which should be paved with a hard surface.
Work example
As an example of work, I will cite the same yard, which encouraged me to create this program. This is the neighborhood of a residential building on Gagarin Avenue in St. Petersburg, in which I used to live and where I regularly walked around. Actually there is a photo of my porch above, where the fence is tied with a ribbon, so my acquaintance with the blasphemy of planners and architects started right from the exit to the street.
This is how this house looks from the satellite. The house itself is in the middle, to the left and to the right of it are panel five-storey buildings. On the right is a marked map of the area indicating the outlines of houses and obstacles.
The scale and outlines of the obstacles are unfortunately rather approximate, since none of the cartographic services known to me contained a detailed plan for this yard, and the satellite images are not detailed enough.
As a result of the simulation, after several hundred iterations, such a picture was drawn. Black marks the programmed lawn trampling points:
For comparison, photos from reality that correspond to the numbered areas:
1 trail diagonally to the corner of the house
2 - path along the whole house
3 - photo from the beginning of the article, trails from the entrance
In general, you can see that the predictions of the program are quite accurate.
Example 2
Well, I confess, I cheated a little and it was in this courtyard that I customized the parameters of the algorithm so as to get an option close to reality. The parameters mainly related to the behavior of pedestrians - the speed of movement, the rate of overgrowing of the trails, the number of pedestrians, etc.
Having adjusted the parameters on this and a couple of other neighboring courtyards, I took up another glaring example of design idiocy - Victory Park. Several years ago, this park underwent redevelopment, in particular, for some reason, instead of a convenient wide road leading through the park from houses to the metro station, they made a huge round lawn, and let the road bypass.
So, the prediction of the program:
And a real satellite image (of course the unhappy lawn impatient citizens trampled so that it became visible even from space):
Of course, there are no smaller paths in this picture, but they are there (in fact, they are even more than the program predicted, but in general the configuration is very similar, I have enough photos, but I’m not going to upload them anyway, and so brute force). Again, a certain discrepancy is due to the inaccuracy of the map - at the time of writing the original article, which was never published, there was still no new map of the park after reconstruction in any map services, it was necessary to draw it from memory and sketches.
findings
And the conclusions are very simple. If somehow we managed to introduce such a tool to the place where we are engaged in designing courtyards, it would be better to live and the grass would become greener. I myself recently moved to the “Baltic Pearl” - a new and modern microdistrict of St. Petersburg - and just grab my head when I see how yard passes are made there. From the satellite probably looks beautiful, but absolutely non-functional. The first photo in the article is from there. Sending appeals to local authorities does not help - officially that area has not yet been transferred to the city, and no one is responsible for it. It was necessary to do right from the start.
But since I like to write code and don’t really like to impose it on someone, I don’t have a clue if I can do something with this situation, and if so, how. Can someone from the browsers tell?
UPD: in the comments ask about the code and the ability to run on their data. For now, the implementation is more likely some kind of proof-of-concept, with a not very friendly interface. Since this topic has caused interest, I will finish it in some more human form and post it a little later.
UPD 2: completed, the application is available on antroadplanner.ru Frontend is not my specialty, so usability is lame in both legs. But you can drive on your data.
I think familiar to all the inhabitants of our cities. Eternally trampled lawns turning into a mud swamp after each rain, through which pedestrians selflessly continue to make their way. Pachkaya while clothing and carrying mud porridge on the pavement.
')
It is obvious that people here are generally not to blame, such is our nature - to always look for the shortest path. And it would be nice if the layout of public areas to meet this aspiration. But this, alas, is not so, and architects and planners with perseverance continue to draw paths and sidewalks along a ruler and with intersections at right angles, and pedestrians cut those corners wherever possible by trampling grass and spreading dirt.
Somehow I walked along the track and sluggishly pondered about the fact that once again I would have to either go around or get my shoes dirty. From a disturbance like “that's what fools design it for,” the thought flowed smoothly onto a bike heard about a certain science city, where the paths in the courtyards were not done at first, and then they simply asphalted people’s footpaths that were convenient for people. And from there, thought migrated to the idea of "why not do the same thing, but on the computer?". Develop a program that, according to a given map, will predict where people will trample lawns and where it would be nice to make asphalt pavement?
Under the cut - a description of the algorithm and a couple of examples of its work for real St. Petersburg courtyards.
To begin with, we will look at how local authorities responsible for landscaping deal with the problem of walking on lawns.
Option One: put fences
In most cases, an inefficient way. The fence will be broken sooner or later. In the photo below it was broken and hung back many times already, throwing out money for nothing.
Option Two: admit error and correct
Yes, it also happens. In this regard, I like the courtyards around Moskovsky Prospekt — the paths there have been turned into normal paths, and no one walks the lawns anymore — there is simply no need for that. However, it all depends on the enthusiasm of local authorities - someone does, someone writes formal replies, promises to make it in 5 years when there will be money, and most often they are trying to fight according to the first method.
Well, option three: to foresee and correct problems at the design stage.
Honestly, I have no idea what designers and developers are doing for this. Judging by the schemes I have seen - nothing, they mold everything based solely on aesthetic considerations. I would be happy if someone with experience in this field can say something in the comments.
This option we will do.
Formulation of the problem
So what do we have? And we have a map of the area on which there are:
- Plots with varying degrees of terrain and attractiveness for pedestrians (paths, lawns)
- Obstacles (houses, fences)
- Places between which pedestrians move - entrances, stalls, shops - anything. They will be called pedestrian generators.
It is necessary to predict exactly where pedestrians will walk on the lawns, so that on the basis of this it could be decided to create normal roads on the site.
We immediately note two boundary cases that usually come to mind first as a solution. The first one is a complete graph, that is, we simply take and connect each generator with each one, building roads in a straight line. In words, simply, pedestrians will, of course, be comfortable, but in the end the whole yard will be rolled up into the asphalt, which is expensive and unaesthetic. The second case is the minimum spanning tree of the graph, the peaks in which will be the generators. Unfortunately, people are still not robots and do not walk on minimal spanning trees, which was shown by researchers to work "Modeling the Evolution of Human Trail Systems" (D. Helbing, J. Keltsch, P. Molnar.) The illustration to this statement can Serve the following image:
The system of full paths is shown on the left, and the system of paths between the points indicated as a result of experiments from the above-mentioned work is shown on the right. It can be seen that it is neither complete nor spanning tree.
As a result of some thoughts and study of articles on the simulation of pedestrian traffic, the following algorithm was invented and implemented.
Algorithm
Training.
The map of the considered area of the territory is presented in the GeoJSON format. On it are manually marked pedestrian generators and cross-sections of the landscape.
Initialization. Based on the map, the navigation graph G (V, E) is constructed. The vertices of the graph V are the set of points of the terrain. In this paper, the simplest method for constructing this set is chosen: a rectangular grid is superimposed on the map, its nodes become the vertices of the graph. If a person can pass between two adjacent grid nodes, such nodes are connected by edges that make up the set E. The initial weight of each edge e is represented as the difference of two components: a fixed Wconst (e) , determined by the type of terrain, and a variable Wvar (e) , which will be called later extrudedness. Initially, it is zero. Some types of terrain (hard surface tracks) may not have a variable component.
Trampling is limited to zero (untouched lawn) from below, and from above, Wmax , selected so that even the most trampled path still is a little less attractive than a similar track.
In addition, for each pedestrian p, the coefficient of decency k (p) is introduced. This coefficient is used to simulate various categories of pedestrians - both “decent”, who always prefer to walk only along the paths, even if the final distance is much larger, and those who like to walk are always straight. The formula for calculating the weight W (e, p) of the edge e for a pedestrian p is:
In this case, if the value of k (p)> 1, the short straightened paths for this pedestrian will be more attractive, since the role of the Wvar component in the formula will be higher. When k <1, you get a “decent” pedestrian who will try to walk along the paths more often.
Simulation.
P pedestrians are evenly distributed on the generators. Goals for them are selected randomly from the list of other generators. The coefficient of decency k (p) is selected as follows:
Here Kbad is an obligatory share of dishonest pedestrians (to speed up the convergence of the algorithm, we assume that there is always a certain proportion of people in the community who want to move in the most direct and short ways), N is the normal distribution. The values of the coefficients are chosen empirically, the value 0.1 is selected for Kbad .
At each step of the simulation, the following actions are performed:
1) pedestrians walk a certain distance depending on a given speed of movement;
2) trampling by the pedestrians of the graph edges increases by a fixed value of ∆Wped for each pedestrian passing through them;
3) pedestrians that have reached their goal are replaced with new ones;
4) trampling of all edges of the graph is reduced by a fixed value ∆Wtime (overgrowing with time).
Thus, the total change in trampling for the edge e after the simulation step i looks like:
Here Pcount (e, i) is the number of pedestrians who passed at the i step along the edge e .
Pedestrians pave a route using the heuristic algorithm A * c to straighten the paths (initially I used the banal Dijkstra, but on rectangular grids he likes to generate rather unnatural-looking paths). The simulation continues either until convergence, until the map of paths stops changing, or a specified number of steps. After the completion of the simulation, the map with the distribution of trampling demonstrates the areas where pedestrians most often go off the tracks to the ground, and which should be paved with a hard surface.
Work example
As an example of work, I will cite the same yard, which encouraged me to create this program. This is the neighborhood of a residential building on Gagarin Avenue in St. Petersburg, in which I used to live and where I regularly walked around. Actually there is a photo of my porch above, where the fence is tied with a ribbon, so my acquaintance with the blasphemy of planners and architects started right from the exit to the street.
This is how this house looks from the satellite. The house itself is in the middle, to the left and to the right of it are panel five-storey buildings. On the right is a marked map of the area indicating the outlines of houses and obstacles.
The scale and outlines of the obstacles are unfortunately rather approximate, since none of the cartographic services known to me contained a detailed plan for this yard, and the satellite images are not detailed enough.
As a result of the simulation, after several hundred iterations, such a picture was drawn. Black marks the programmed lawn trampling points:
For comparison, photos from reality that correspond to the numbered areas:
1 trail diagonally to the corner of the house
2 - path along the whole house
3 - photo from the beginning of the article, trails from the entrance
In general, you can see that the predictions of the program are quite accurate.
Example 2
Well, I confess, I cheated a little and it was in this courtyard that I customized the parameters of the algorithm so as to get an option close to reality. The parameters mainly related to the behavior of pedestrians - the speed of movement, the rate of overgrowing of the trails, the number of pedestrians, etc.
Having adjusted the parameters on this and a couple of other neighboring courtyards, I took up another glaring example of design idiocy - Victory Park. Several years ago, this park underwent redevelopment, in particular, for some reason, instead of a convenient wide road leading through the park from houses to the metro station, they made a huge round lawn, and let the road bypass.
So, the prediction of the program:
And a real satellite image (of course the unhappy lawn impatient citizens trampled so that it became visible even from space):
Of course, there are no smaller paths in this picture, but they are there (in fact, they are even more than the program predicted, but in general the configuration is very similar, I have enough photos, but I’m not going to upload them anyway, and so brute force). Again, a certain discrepancy is due to the inaccuracy of the map - at the time of writing the original article, which was never published, there was still no new map of the park after reconstruction in any map services, it was necessary to draw it from memory and sketches.
findings
And the conclusions are very simple. If somehow we managed to introduce such a tool to the place where we are engaged in designing courtyards, it would be better to live and the grass would become greener. I myself recently moved to the “Baltic Pearl” - a new and modern microdistrict of St. Petersburg - and just grab my head when I see how yard passes are made there. From the satellite probably looks beautiful, but absolutely non-functional. The first photo in the article is from there. Sending appeals to local authorities does not help - officially that area has not yet been transferred to the city, and no one is responsible for it. It was necessary to do right from the start.
But since I like to write code and don’t really like to impose it on someone, I don’t have a clue if I can do something with this situation, and if so, how. Can someone from the browsers tell?
UPD: in the comments ask about the code and the ability to run on their data. For now, the implementation is more likely some kind of proof-of-concept, with a not very friendly interface. Since this topic has caused interest, I will finish it in some more human form and post it a little later.
UPD 2: completed, the application is available on antroadplanner.ru Frontend is not my specialty, so usability is lame in both legs. But you can drive on your data.
Source: https://habr.com/ru/post/257563/
All Articles