Street dirt and pedestrian simulation

    With the advent of spring and rain on the street, one problem is increasingly striking. This one:



    I think it’s familiar to all residents of our cities. Forever trampled lawns, turning into a mud swamp after every rain, through which pedestrians continue to make their way selflessly. Dirty clothes and taking mud porridge onto the asphalt.

    Obviously, 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 territories meets this aspiration. But this, alas, is not the case, and architects and planners stubbornly continue to draw paths and sidewalks in a ruler and with intersections at right angles, and pedestrians cut these corners wherever possible, trampling grass and spreading dirt.

    I once walked along the path and thought languidly on the topic of the fact that again I would have to either drag around, or get my shoes dirty. With indignation such as “fools are designing this,” the thought flowed smoothly to a once heard tale about a certain science city, where paths in the courtyards were not made at all at first, and then they simply paved the paths trodden by people and got a network of convenient routes for residents. And from there the thought migrated to the idea of ​​“why not do the same, but on the computer?” To develop a program that, according to a given map, will predict where people will trample on lawns and where it would be nice to make asphalt?

    Under the cut - a description of the algorithm and a couple of examples of its work for real Petersburg yards.


    To begin with, we will consider how generally the local authorities responsible for landscaping struggle with the problem of walking on lawns.

    Option one: put up fences
    In most cases, an ineffective way. The fence will be broken sooner or later. In the photo below, they broke it and hung it back many times, throwing away wasted money.



    Option two: admit the mistake and fix.
    Yes, that also happens. In this regard, I like the yards around Moskovsky Prospekt - there they turned the paths into normal paths, and no one else walks on the lawns - there is simply no need for that. However, it all depends on the enthusiasm of the local authorities - someone does, someone writes unsubscribes, promises to do in 5 years when there is money, and most often they try to fight according to the first method.



    Well, there’s the third option: to foresee and fix problems at the design stage
    Honestly, I have no idea what designers and developers are doing for this. Judging by the schemes I saw - nothing, they sculpt everything guided exclusively by aesthetic considerations. I would be glad if in the comments someone with experience in this area can tell something.
    We will be engaged in this option.

    Problem statement
    So what do we have? And we have a map of the area on which there are:
    • Land plots with varying degrees of cross-country ability and attractiveness for pedestrians (paths, lawns)
    • Obstacles (houses, fences)
    • Places between which pedestrians move - porches, stalls, benches - anything. They will be called pedestrian generators

    It is necessary to predict exactly where pedestrians will walk on the lawns, so that on this basis it would be possible to decide on the creation of normal roads in place of paths.

    We immediately note two edge cases that usually come to mind first as a solution. The first is a complete graph, that is, we just take and connect each generator with each, paving the roads in a straight line. In words, it’s simple, it will be convenient for pedestrians, of course, but in the end the whole yard will be rolled into asphalt, which is expensive and unaesthetic. The second case is the minimal spanning tree of the graph, the vertices in which will be the generators. Unfortunately, people are still not robots and do not walk on minimal spanning trees, which was shown by the researchers of Modeling the Evolution of Human Trail Systems (D. Helbing, J. Keltsch, P. Molnar.) An illustration of this statement can serve the following image:

    The system of full paths is shown on the left, and the system of paths between the indicated points obtained as a result of experiments from the above work is shown on the right. It can be seen that it is neither a complete tree nor a spanning tree.

    As a result of some reflection and study of articles on the subject of pedestrian traffic simulation, the following algorithm was invented and implemented.

    Algorithm

    Preparation.
    A map of the considered area is presented in the GeoJSON format. Pedestrian generators and terrain patches are manually marked on it.

    Initialization. Based on the map, a navigation graph G (V, E) is built . Vertices of graph V- This is a lot of terrain points. In this paper, the simplest method for constructing this set has been chosen: a rectangular grid is superimposed on the map, its nodes become vertices of the graph. If between two neighboring grid nodes can pass people, these nodes are connected to the ribs forming the set E . The initial weight of each edge e is presented in the form of the difference of two components: a fixed Wconst (e) , determined by the type of terrain, and a variable Wvar (e) , which in what follows will be called trampled. Initially, it is zero. Some terrain types (hard-coated tracks) may not have a variable component.
    Trample is limited from below to zero (untouched lawn), and from above by the number Wmax, selected in such a way that even the most trampled path was still a little less attractive than a similar path.
    In addition, a decency coefficient k (p) is introduced for each pedestrian p . This coefficient is used to simulate various categories of pedestrians - both “decent” ones who always prefer to walk only along paths, even if the total distance will be much greater, and those who like to walk are always straightforward. The formula for calculating the weight W (e, p) of the edge e for the pedestrian p has the form: In this case, with the value k (p)> 1

    short straightened paths for this pedestrian will have great attractiveness, since the role of the Wvar component in the formula will be higher. For k <1 , a “decent” pedestrian is obtained, who will try to walk along the tracks more often.

    Simulation.
    P pedestrians are evenly distributed over the generators. The goals for them are randomly selected from the list of other generators. The decency coefficient k (p) is selected as follows:

    Here Kbad is the obligatory share of dishonest pedestrians (to accelerate the convergence of the algorithm, suppose that in society there is always a certain percentage of people who like to travel in the most direct and short ways), N- normal distribution. The values ​​of the coefficients are selected empirically; for Kbad, the value 0.1 is chosen.

    At each step of the simulation, the following actions are performed:
    1) pedestrians travel a certain distance, depending on a given speed;
    2) the trample of the edges of the graph passed by pedestrians increases by a fixed value ∆Wped for each pedestrian passing through them;
    3) pedestrians who have reached their goal are replaced by new ones;
    4) the trample of all edges of the graph decreases by a fixed value ∆Wtime (overgrowing with time).
    Thus, the total change in trample for the edge e after the simulation step i looks like:

    HerePcount (e, i) - the number of pedestrians walking at step i along the edge e .
    Pedestrians make a route using the A * algorithm with a heuristic to straighten paths (I originally used the banal Dijkstra, but on rectangular grids he likes to generate rather unnatural looking paths). The simulation continues either until convergence, until the path map stops changing, or a given number of steps. After the simulation is completed, the map with the distribution of trampling shows the areas on which pedestrians most often go off the tracks to the ground, and which should be paved with hard surface.

    Work example

    As an example of work, I will cite the very courtyard that encouraged me to create this program. This is the neighborhood of a residential building on Gagarin Avenue in St. Petersburg, where I used to live and where I regularly cursed. Actually, there is a photo of my staircase above, where the fence is tied with a ribbon, so that the acquaintance with the headshots of planners and architects began right on the street.

    This is how this house looks from the satellite. The house itself in the middle, to the left and to the right of it - panel five-story buildings. On the right is a marked map of the area showing the outlines of houses and obstacles.



    The scale and shape of the obstacles are unfortunately quite approximate, since none of the photographic services known to me contained a detailed plan of this yard, and satellite images are not detailed enough.

    As a result of the simulation, after several hundred iterations, such a picture was drawn. Black marks the places predicted by the program for trampling lawns:



    For comparison, photos from reality corresponding to numbered sections:

    1 path diagonally to the corner of the house


    2 - path along the entire house


    3 - photo from the beginning of the article, paths from the entrance


    On the whole, you can see that the predictions of the program are quite accurate.

    Example 2

    Okay, I admit, I cheated a little and it was in this yard that I adjusted the parameters of the algorithm in such a way as to get a version close to reality. The parameters mainly related to the behavior of pedestrians - the speed of movement, the rate of overgrowing of trails, the number of pedestrians, etc.

    Adjusting the parameters for this and a couple of other neighboring yards, I took up another glaring example of design idiocy - Victory Park. A few years ago this park was redeveloped, in particular, for some reason, instead of a convenient wide road leading through the park from the houses to the metro station, they made a huge round lawn, and let the road go around.

    So, the program’s prediction:



    And a real satellite image (of course, impatient citizens trampled the miserable lawn in such a way that it became clear even from space):



    Of course, smaller paths are not visible in this picture, but they are there (in fact, there are even more of them than the program predicted, but in general the configuration is very similar, I have enough photos, but here I will not upload them, and so perhaps bust). A certain discrepancy is again due to the inaccuracy of the map - at the time of writing the original article, which had not yet been published, in all map services there was no new map of the park after reconstruction, it was necessary to draw it from memory and sketches.

    conclusions

    And the conclusions are very simple. If somehow it was possible to introduce such a tool where they are engaged in the design of courtyards - life would become better and the grass would become greener. I myself recently moved to the “Baltic Pearl” - a new and modern microdistrict of St. Petersburg - and I just grab my head when I see how courtyard passages are made there. It probably looks beautiful from a satellite, but it’s 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 from the very beginning to do it right.

    But since I like to write code and don’t really like to impose it on anyone later, I have no idea if something can be done with this situation, and if so, how. Can someone from habrazhitel prompt?

    UPD: in the comments they ask about the code and the ability to run on their data. While the implementation is rather a kind of proof-of-concept, with a not-so-friendly interface. Since this topic has aroused interest, I will complete it in some more human form and post it a bit later.

    UPD 2: completed, the application is available on antroadplanner.ru The frontend is not my specialty, so usability is limping on both legs. But you can drive on your data.

    Also popular now: