Вебсервис для симуляции движения пешеходов и выявления проблем благоустройства

    Некоторое время назад я опубликовал тут свою статью, посвященную проблеме благоустройства дворов: habrahabr.ru/post/257563
    В статье рассматривался алгоритм, позволяющий по плану местности предсказать, где пешеходы будут сходить с дорожек и топать по газонам, разнося грязь и портя всю красоту. Алгоритм представлял собой симуляцию движения пешеходов на заданной местности с помощью доработанного A* и модифицируемого во время движения навигационного графа.

    Тема неожиданно заинтересовала посетителей хабра, в комментариях многие высказали пожелание попробовать запустить алгоритм на своих данных. В итоге я сделал реализацию алгоритма в виде вебсервиса. Под катом будет описание его возможностей, пошаговая инструкция а также некоторые детали реализации. Приглашаю всех протестировать работу сервиса и алгоритма, ну и использовать ее в своих проектах по возможности.

    Продемонстрирую процесс применения сервиса на примере вот этого участка проспекта Стачек в Санкт-Петербурге:



    Сам этот участок — замечательный пример того как не надо проектировать жилые районы. Вполне возможно что неудачная планировка обусловлена фактом что когда-то кроме шоссе рядом ничего и не было, а теперь там крупный жилой массив. Не знаю. Но факт таков, что вдоль него все очень плохо с наличием тротуаров, переходов и пешеходных дорожек. И даже на спутниковом снимке видны широкие народные тропы через газоны. Посмотрим, выдаст ли алгоритм что-то похожее на ситуацию в действительности.


    Сразу призанюсь что фронтенд — не моя специализация, поэтому некоторые вещи я делал впервые, а интерфейс наверное оставляет желать лучшего. А сам сервис запущен на бесплатном плане Heroku и под хабраэффектом может лечь. Увы, лишних средств на оплату нормального хостинга у меня пока не предвидится.

    Итак, чтобы нарисовать свою карту идем на http://antroadplanner.herokuapp.com/tasks/editor

    Редактор сделан на основе Яндекс.Карт. Почему именно этот картографический сервис? Потому что все-таки у них карта России обновляется чаще и более подробна. К примеру Парк Победы, упомянутый в прошлой статье, у них содержит обновленный вид, после реконструкции, в то время как карты гугла и OSM все еще рисуют устаревший план.

    Итак, приcтупим к рисованию карты.

    Справа находится панель инструментов, которые позволяют добавлять объекты на карту: препятствия и генераторы пешеходов. С точки зрения API карт нажатие на каждую кнопку приводит к вызову
    currentPoly = new ymaps.Polygon(...) // Создается полигон и ему назначаются стили рисования в зависимости от типа препятствия
    currentPoly.editor.startDrawing() //Собственно вся логика редактирования здесь
    

    Раньше с картами я не работал и поэтому мне очень понравилась легкость редактирования. Всю заботу о работе с вершинами и линиями, обработку кликов апи берет на себя. Очень удобно.

    Для начала разметим основные препятствия — дома и группы деревьев. Люди не очень любят ходить между плотно стоящими стволами. Используем для этого инструменты «здания» и «растительность» с панели препятствий.

    Затем разметим автомобильные дороги. Это особый вид препятствия: пешеходы не будут ходить по проезжей части вдоль, но смогут ее пересекать поперек.
    Как показал опыт тестирования, наибольшее недоумение вызывает именно разница между типами местности «автомобильная дорога» и «пешеходная дорожка» так как и то, и другое чаще всего является поверхностью с асфальтовым покрытием, но вот смысл с точки зрения симуляции у них принципиально разный.
    • Автомобильная дорога — это проезжая часть крупных улиц. Пешеходы не ходят по ней «вдоль», а только пересекают.
    • Пешеходная дорожка — это все те места где пешеходы могут ходить в любом направлении. Это не только собственно дорожки, но и, например, внутриквартальные проезды или парковки.


    Вот как выглядит карта после разметки основных препятствий:



    Теперь нужно добавить дорожки и тротуары. Отдельно стоит отметить пешеходные переходы — они должны быть сделаны разрывом в препятствии «дорога» с проложенной внутри пешеходной дорожкой. Не очень удобно, да, но пока так.

    После добавления дорожек настает черед добавить генераторы пешеходов — все те места, между которыми они будут передвигаться по нашей карте. В случае рассматриваемого участка это будет:
    1) Входы в магазин Максидом (самое большое здание справа-сверху), автосалон и несколько мелких зданий
    2) Две остановки трамвая и автобусов вдоль шоссе
    3) Все дорожки, ведущие за пределы рассматриваемой зоны.

    Генераторы могут быть «большие» и «обычные», отличающиеся количеством генерируемого во время симуляции траффика. Большим в данном случае отметим Максидом и парковку вокруг него.

    Вот так выглядит итоговая карта. Дорожки отмечены светло-серым, генераторы — коричневым.



    Остался один небольшой штрих — указать точные границы зоны симуляции. Без этого некоторые шибко умные пешеходы могут воспользоваться отсутствием размеченных окрестностей по соседству — ведь сейчас получается что наша карта как бы стоит «в чистом поле» — и обойти препятствия выйдя за пределы интересующей нас области. Для этого воспользуемся элементом «граница».

    Итак, карта готова, отправляем на обработку. Опционально можно указать свой email, на который придет извещение о результатах.



    Вычисления

    Симуляция может занять длительное время (до получаса), поэтому результаты недоступны сразу же. Для вычислений используется распределенная сеть, построенная с помощью фреймворка JPPF. В итоге после отправки карты веб-сервер просто складывает ее в базу данных и ждет пока станет доступен сервер вычислений. Я время от времени запускаю его на своих домашних машинах, но возможности держать его включенным постоянно у меня нет.
    Установив соединение с сервером вычислений, вебсервер начинает слать ему задачи, а тот раскидывает их исполнение по вычислительным нодам, а затем собирает результаты.

    Вообще JPPF довольно полезная штука, я уже много лет пользуюсь ей в разных проектах требующих длительных вычислений, начинал с версии 2, а теперь там уже 5-с-чем-то. Она включает в себя управляющие сервера, вычислительные ноды, тулзы для мониторинга, с недавних пор работает уже и на андроиде (хотя я слабо представляю кто захочет считать на андроиде что-то тяжелое, долгое и жрущее батарею). Позволяет гибко настраивать требования к нодам при запуске задачи, в общем имеет все чего можно ожидать от подобного решения для распределенных вычислений. Кроме разве что стабильности — она с годами почему-то не улучшается.

    В данный момент я могу позволить запустить вычислительные ноды на двух своих машинах. У меня уже спрашивали можно ли подключить свои собственные ноды чтобы помочь проекту. Вот тут я в некотором затруднении. С одной стороны технически ничего сложного в этом нет — достаточно скачать архив с офсайта, прописать в конфиге IP сервера и запустить. С другой — я пока так и не разобрался как защитить сервер от запуска «чужих» задач. Так как если открыть его адрес наружу то на него кто угодно сможет слать свои задания, фактически удаленно выполняя код на нодах. Наверное это не очень безопасно с точки зрения владельцев этих нод (да, конечно, виртуальная машина джавы, security manager, все дела, но кто поручиться что через них нельзя пролезть куда не надо?).

    Итак, вычисления завершены, их результат можно увидеть либо по ссылке в письме, либо введя ID карты в форму в хедере сайта.

    И что же мы видим: а видим мы примерно то же что и на спутниковом снимке. Программа показал что людям очень хочется ходить от остановок прямо в сторону Максидома, что очень не хватает тротуара идущего вдоль шоссе и люди ходят по большому газону вдоль (эту тропинку можно разглядеть и на яндекс карте, хотя надо приглядеться).



    Ну вот не хотят люди поворачивать под прямыми углами! Поэтому люди от остановок транспорта стремятся идти по диагонали, напрямик к цели. Что отлично видно как на сгенерированном алгоритмом плане, так и на реальном спутниковом снимке.

    Конечно, полученный результат не идеален. Отчасти это определяется неточностями размеченной нами карты (иногда даже положение одного отдельного дерева может заметно изменить картину дорожек), отчасти — загадочностью человеческой природы и не полным соответствием ей компьютерной модели. Поэтому я не предполагаю пока делать дорожки ровно там где алгоритм это предлагает. Но уже сейчас он может служить мощным средством для обнаружения проблем в планировке.

    Заключение

    Итак, вебсервис сделан, приглашаю всех заинтересованных протестировать и использовать. Там еще много работы как по части интерфейса, так и по части алгоритма, но я надеюсь что уже даже в таком виде он способен предостеречь проектировщиков от совершения типичных ошибок.

    Потрогать рассмотренную в статье карту можно по ссылке antroadplanner.herokuapp.com/tasks/taskstatus?jobId=5720d88ca9855a0003cc72b0 (чтобы увидеть исходную карту надо нажать на кнопку «редактировать карту» внизу)

    Справка (помимо примера там еще есть формат входных данных и инструкции по импорту данных из OSM) antroadplanner.herokuapp.com/application/editorhelp

    Блог, в котором я пишу об обновлениях сервиса, примерах работы и всяких мыслях на тему благоустройства:
    antroadplanner.wordpress.com

    UPD 1: Для тех кто получает ошибку «карта не является связной»: если граница карты не нарисована вручную, то за границу принимается bounding box всей геометрии. При этом если у вас есть идущее через всю карту длинное здание — BB будет построен по его краям, при этом карта разобьется на две несвязанные области. Поэтому границу лучше рисовать всегда, оставляя в таком случае зазоры по краям.

    UPD 2: Для тех, кому лень вручную расставлять здания — можно воспользоваться импортом данных из OSM. Для этого надо сконвертировать фрагмент OSM-карты в GeoJSON формат (например с помощью тулзы JOSM) и загрузить его в редактор. Правда такие карты требуют ручной доработки: необходимо расставить генераторы пешеходов и подправить дороги, так как в OSM дороги не имеют толщины и задаются линиями, а не полигонами
    Вот пример большой и сложной карты, полученной из данных OSM:

    image
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 51
    • +2
      Насколько я понимаю, раз исходные данные берутся с сервисов Яндекс Карт, то конечный результат является производной работой, то есть его создание нарушает лицензионное соглашение Яндекса. Что бы избежать такого нарушения — подложите в редактор карт одну из подложек Openstreetmap.
      • 0
        Ну тут тонкий вопрос. На самом деле исходные данные у яндекса я не беру. Я всего лишь рисую их карту как фон для своего редактора, а рисовать поверх нее вы можете все что угодно. И в симуляции используются только нарисованные пользователем данные.

        Поглядел https://yandex.ru/legal/maps_api/ — там ничего не сказано про запрет производных работ. Есть некоторые ограничения (нельзя делать проекты ради дохода, или игровые проекты), но вроде бы ничего такого, подо что мой сервис бы попадал.
      • 0
        судя по фото некоторые преодолевают участок с лесом, вообщем ты не ты когда голоден а магазин через 2 шоссе и лесополосу.
        • 0
          Ну там не лес, просто группа деревьев. Между ними не так сложно пройти.
          С деревьями вообще спорная ситуация: иногда они служат препятствием (когда много деревьев растут рядом — люди их обходят), а иногда — наоборот аттрактором (в жаркую погоду лучше пройтись в тенечке). Я пока так и не решил что с этим делать.
          • 0
            да я понял, это сложно учесть просто по карте. Другая фишка так это не учтены источники трафика с другой стороны, по хорошему нужно каждый подъезд пометить.
            • 0
              В целом да, для получения более точной карты желательно как можно больше всего на нее нанести и точнее ее отрисовать. И иногда даже небольшие изменения в исходных данных могут привести к серьезным изменениям в рисунке дорожек.

              Кто-то (вы?) кстати уже заслал модифицированную карту из статьи — http://antroadplanner.herokuapp.com/tasks/taskstatus?jobId=57346ccaed39ae00034da4cf и на ней стала видна еще одна дорожка из реальности, ведущая от проезда через газон поперек.

              Кстати выходит так, что сервис еще может дать подсказку на тему того где стоило бы организовать пешеходный переход. Правда если уж дорожки у нас худо-бедно делают, то вынудить власти сделать переход (и уж тем более — регулируемый) это вообще Mission Impossible (сужу по отзывам знакомых и историям в интернете).
              • 0
                Не, это не я!
                • +1
                  Случайно промазал и отклонил комментарий про пешеходные переходы который тут был. Вообще неплохо бы при отклонении запрашивать подтверждение.
                • +2
                  //то вынудить власти сделать переход (и уж тем более — регулируемый) это вообще Mission Impossible (сужу по отзывам знакомых и историям в интернете).
                  Имею небольшой опыт, даже не перехода а «продолжения перехода на внутридомовой дороге». Год переписки, отказ-жалоба на отказ -… и, неожиданно, переход сделали. Правда, есть подозрения, что это просто случайно совпало. Хотя, «На основании вашей жалобы… принято решение ...».
                  Но, действительно, сложно. Так как, дорожку может и ЖКУ сделать, а переход делает контора при администрации по согласованию с ГАИ.
              • 0
                Скорее всего причина в высоте первых веток над землей у конкретной группы деревьев. Если выше среднего роста, то будут ходить к цели под этими деревьями…
            • +8
              Что-то симулированные пешеходы не очень радикальны — не совсем по прямой срезают
              image
              • +3
                Пешеходы вытоптали символ сатаны… хмм как-то это подозрительно))
                • +2
                  Все зависит от ракурса. Может оказаться, что на самом деле это не символ сатаны, а, например, звезда.
                • 0
                  Думаю нужно учитывать рельеф (в примере из поста)
                  • 0
                    А он там ровный.
                    Хотя в целом да, надо бы, но это не так просто, из карты эти данные не выцепить. Разве что лично там походить и увидеть где есть крутые склоны и всякое такое.
                    • 0
                      На спутниковом снимке видно что люди идут напрямую по газону — часть идёт к ближнему входу в тц, часть к дальнему, вдоль «леса». На симуляции — все идут по диагонали, вроде как к ближайшему тротуару, это странно.
                      • 0
                        Там на самом деле нет входа. Вход в Максидом там один со стороны парковки.
                        Иногда такое бывает — почему-то вместо одной тропы образуется две рядом. Не очень понятно почему.
                        Впрочем поэтому я и не говорю что алгоритм идеально точно подходит для проектирования дорожек, во всяком случае пока. Он скорее позволяет выявить проблемы и показать их проектировщику (то есть сам факт того что люди вот тут будут хотеть ходить напрямую). А конкретное положение дорожки пока придется выбирать человеку.
                        • 0
                          Предположу, что это из-за погодных условий:
                          — если дорожка вытоптана до земли, то после дождя там будет грязь и местами лужи — проще обойти по травке рядом.
                          — после зимы дорожки тоже смещаются, а старые «версии» не успевают покрыться травой.
                  • 0
                    А пешеходы не всегда ходят по прямой. Так как обычно лучше пройти чуть дальше, но по асфальту или уже готовым тропам, чем переть напрямик по грязи.
                    • 0
                      Вчера специально вдумчиво ходил тропами, которые получились естесственным путем. Есть догадка, почему не всегда человек идет к цели по прямой а по дуге — возможно хочется видеть дальнейший путь и возможные опасности чуть раньше, чем возможно дойти до препятствия, за которым следует поворот или слепая зона.
                      • 0
                        у людей есть что-то типа инерции — напр дыру в заборе проходят перпеникулярно, и только мётра через 3 возращаются на «директриссу»
                        • 0
                          Где-то было исследование, что человек обычно может отклониться от тропы к конкретной точке, если между маправлением тропы и целевым направлением (точнее той точкой в прямой видимости, куда вы хотите придти) угол превышает приблизительно 30-35 градусов.

                          Т.е. если в той конкретной точке, где находится пешеход, цель и тропа расходятся меньше чем на 30 град., то пешеход скорее всего пойдет по тропе. А если больше — высока вероятность того, что срежет.

                          • 0
                            Да, в прошлой теме мне уже кидали ссылку. Я правда пока не придумал как это применить. Вообще судя по результатам некоторых симуляций алгоритм поиска пути надо будет менять. А* в некоторых ситуациях рисует может и кратчайшие, но неправдоподобно выглядящие пути.
                      • 0
                        В одной из отправленных хабрающерами карт получилось что-то похожее, кстати, почти звезда. Но вообще это вырожденный случай полного графа дорог. когда из каждой точки в каждую напрямик ходят.

                        image
                      • 0
                        А исходный код бекенда закрыт и не будет открыт?
                        • 0
                          Все открыто — https://bitbucket.org/e_smirnov/antpathplanning
                          Правда никакого Rocket Science там нет, и в прошлой статье алгоритм работы я подробно описал.
                        • 0
                          А если попробовать сделать начальную расстановку некоторых начальных элементов автоматом, отталкиваясь от карты типа «схема»?
                          Правда, для этого придётся проводить анализ картинки и разбирать по цвету, но при наложении это может неплохо поспособствовать начальному автозаполнению.
                          Если решите выложить на github/bitbacket, то люди могли бы с удовольствием подключиться к данной разработке. Меня это заинтересовало по крайней мере.
                          • 0
                            Вот ссылка на репозиторий https://bitbucket.org/e_smirnov/antpathplanning
                            Сейчас можно из OSM импортировать данные — здания и дороги. Но вопрос в их правильности и подробности. Если дома еще нормально указаны обычно, то дорожки дворовые уже мало где подробно сделаны.
                          • 0
                            Всё хорошо, только это проспект Стачек, а не Петергофское шоссе =) шоссе после Жукова начинается =)
                            • 0
                              и все таки это проспект Стачек
                              • 0
                                Очень круто!
                                Id уже рассчитанных карт не простой порядковый номер? добавьте, если можно, возможность просмотреть уже просчитанные чужие карты, вроде ничего секретного в этом нет.
                                • 0
                                  Это MongoDBшный id. А список карт можно увидеть на http://antroadplanner.herokuapp.com/tasks/list

                                  Вообще карт заслали сейчас очень много, но большинство из них бессмысленны. Похоже люди зашли, потыкали в кнопочки наугад и отправили. В итоге куча каких-то случайных полигонов.
                                • 0
                                  Как где-то писал Лебедев — чтобы пешеходы не вытаптывали газон, не нужно делать изначально никаких дорожек и тротуаров. Оставить как есть на время. Где появятся тропинки — закатать в асфальт (положить плитку).
                                  • 0
                                    Увы, на такие эксперименты у нас вряд ли пойдут. К тому же это все равно приносит определенное неудобство — ведь первое время, пока дорожки не протопчутся, ходить все равно придется по грязи. А так все было бы уже сразу сделано к моменту появления жильцов.
                                    • +1
                                      Подобный подход при организации дорожек на территории НИИ приписывали Курчатову, за много лет до того, как кто-то вообще узнал, кто такой Лебедев.
                                      • 0
                                        Ну так и не то, чтобы это очень сложная мысль была. Тут скорее воля сделать именно так необходима
                                    • 0
                                      Что-то мне подсказывает, что вы решаете систему нелинейных алгебраических уравнений методом монте-карло+итерация по правой части. Выписать бы её аккуратно и натравить метод Ньютона, например — и можно в браузере решать javascript-ом.
                                      • +2
                                        Да то что я делаю и так можно в браузере джаваскриптом сделать, алгоритм-то довольно простой. Тут вопрос не в том что я что-то нереально сложное изобрел, а в том что это похоже раньше было никому не интересно взять и реализовать.
                                      • +1
                                        Совершенно случайно некоторые дороги в OSM содержат данные о полосности (не все, к большому сожалению) из которых можно позаимствовать ширину. Также, преобразование дорог из осевых линий в полигоны делается построением буфера (стандартная операция любой приличной БД с пространственными функциями) и объединением получившейся геометрии.
                                        • 0
                                          Визуализация наличия данных о полосности есть тут. Только сервер немного тормозит, а на односторонних участках проезжей части карта показывает неправильное (удвоенное) количество полос.
                                          • 0
                                            А я так и делаю — в смысле рисую буфер вокруг OSM-ных дорожек. Но толщина этого буфера берется с потолка и может не соответствовать действительности, а это может серьезно влиять на результат.
                                          • 0
                                            самое частое препятствие в городе для пешеходов (на тротуаре, переходе) — лужа. Часто живут годами, если не десятилетиями. Часто система тропинок продиктована в основном ими. Увы малопрогрнозируемы.
                                            • 0
                                              для этого в редакторе, как я понял, и есть непроходимые места: вода. Я так на своей карте «вечную» лужу обозначил
                                              • 0
                                                И как оно, похоже на правду посчиталось? А то уже 400 карт сервис обсчитал (правда там большей частью мусор типа «зашли и потыкали наугад»), а конкретных отзывов пока никто не оставил.
                                                • 0
                                                  Ждем. Там должны появиться 2 тропинки, появятся — расскажу :)
                                                  • 0
                                                    Итак, как и обещал, рассказываю:
                                                    1. Из двух тропинок сервис нашел одну. Вторую он не нарисовал. Либо его так напугали кусты, либо есть еще факторы появления там тропинки
                                                    2. Он нашел еще 2 тропинки о которых я «не знал» (забыл). Мне пришлось пойти на местность, чтобы понять есть они там или нет. Они там были.
                                                    3. Пока гулял, нашел еще одну тропинку — через забор. Люди просто перешагивали через 50 сантиметровый забор, в основном молодежь.

                                                    Т.ч. сервис показал интересные результаты на реальном примере. Надо увеличить площадь и позапускать еще несколько раз.
                                                    • 0
                                                      Спасибо за отзыв! А можно ссылку на вашу карту?
                                                      Маленькие заборчики стоит рисовать как проходимые препятствия, да, люди через них спокойно шастают.
                                              • 0
                                                Тут выше уже писали про «грязь» но как-то не явно. Я лишь хочу подчеркнуть, что часто препятствием является не только лес и кусты, но и просто мокрое место. Его на спутниковых картах может и не быть видно — там та же трава, но там мокро, ноги утопают, ботинки «засасывает» и т. п. Не уверен, что для любых городов, но для того же Санкт-Петербурга это очень актуально. Выходом может быть поиск физической карты местности (с высотами над уровнем моря) и поиск в ней замкнутых низин, которые теоретически могут быть такими мокрыми местами.
                                                • 0
                                                  Это нереально. Никакая карта не даст такой точности чтобы лужу на тротуаре/газоне можно было найти. Да и образуются они как правило там где нормальную канализацию не сделали, а это опять же сложно предсказать.
                                                  Но чисто по моему опыту это не такое уж частое явление. В большинстве случаев люди спокойно проходят там, где хотят пройти, ведь речь обычно не о заливных лугах, а о десятке метров пустыря с пожухлой травкой между подъездами дома.
                                                • 0

                                                  В OSM бывают и двумерные дороги — те, что нарисованы полигонами и имеют свойство area: yes. Кроме того, у дорог в OSM может быть указана ширина width и число полос lanes.

                                                  • 0
                                                    Возможно, но мне такие пока не попадались. Те куски карт что я смотрел этих данных не содержали. Так что рассчитывать на них не приходится.

                                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.