В статье рассматривался алгоритм, позволяющий по плану местности предсказать, где пешеходы будут сходить с дорожек и топать по газонам, разнося грязь и портя всю красоту. Алгоритм представлял собой симуляцию движения пешеходов на заданной местности с помощью доработанного 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:
Комментарии (50)
roboter
12.05.2016 15:01судя по фото некоторые преодолевают участок с лесом, вообщем ты не ты когда голоден а магазин через 2 шоссе и лесополосу.
JediPhilosopher
12.05.2016 15:02Ну там не лес, просто группа деревьев. Между ними не так сложно пройти.
С деревьями вообще спорная ситуация: иногда они служат препятствием (когда много деревьев растут рядом — люди их обходят), а иногда — наоборот аттрактором (в жаркую погоду лучше пройтись в тенечке). Я пока так и не решил что с этим делать.roboter
12.05.2016 15:11да я понял, это сложно учесть просто по карте. Другая фишка так это не учтены источники трафика с другой стороны, по хорошему нужно каждый подъезд пометить.
JediPhilosopher
12.05.2016 15:15В целом да, для получения более точной карты желательно как можно больше всего на нее нанести и точнее ее отрисовать. И иногда даже небольшие изменения в исходных данных могут привести к серьезным изменениям в рисунке дорожек.
Кто-то (вы?) кстати уже заслал модифицированную карту из статьи — http://antroadplanner.herokuapp.com/tasks/taskstatus?jobId=57346ccaed39ae00034da4cf и на ней стала видна еще одна дорожка из реальности, ведущая от проезда через газон поперек.
Кстати выходит так, что сервис еще может дать подсказку на тему того где стоило бы организовать пешеходный переход. Правда если уж дорожки у нас худо-бедно делают, то вынудить власти сделать переход (и уж тем более — регулируемый) это вообще Mission Impossible (сужу по отзывам знакомых и историям в интернете).roboter
12.05.2016 15:26Не, это не я!
JediPhilosopher
12.05.2016 15:32+1Случайно промазал и отклонил комментарий про пешеходные переходы который тут был. Вообще неплохо бы при отклонении запрашивать подтверждение.
Bobak
12.05.2016 15:55+2//то вынудить власти сделать переход (и уж тем более — регулируемый) это вообще Mission Impossible (сужу по отзывам знакомых и историям в интернете).
Имею небольшой опыт, даже не перехода а «продолжения перехода на внутридомовой дороге». Год переписки, отказ-жалоба на отказ -… и, неожиданно, переход сделали. Правда, есть подозрения, что это просто случайно совпало. Хотя, «На основании вашей жалобы… принято решение ...».
Но, действительно, сложно. Так как, дорожку может и ЖКУ сделать, а переход делает контора при администрации по согласованию с ГАИ.
Rumlin
16.05.2016 13:45Скорее всего причина в высоте первых веток над землей у конкретной группы деревьев. Если выше среднего роста, то будут ходить к цели под этими деревьями…
scv0
12.05.2016 16:35+8Что-то симулированные пешеходы не очень радикальны — не совсем по прямой срезают
TimsTims
12.05.2016 17:07+3Пешеходы вытоптали символ сатаны… хмм как-то это подозрительно))
wickedweasel
12.05.2016 17:24+2Все зависит от ракурса. Может оказаться, что на самом деле это не символ сатаны, а, например, звезда.
scv0
12.05.2016 18:11Думаю нужно учитывать рельеф (в примере из поста)
JediPhilosopher
13.05.2016 03:24А он там ровный.
Хотя в целом да, надо бы, но это не так просто, из карты эти данные не выцепить. Разве что лично там походить и увидеть где есть крутые склоны и всякое такое.scv0
13.05.2016 12:54На спутниковом снимке видно что люди идут напрямую по газону — часть идёт к ближнему входу в тц, часть к дальнему, вдоль «леса». На симуляции — все идут по диагонали, вроде как к ближайшему тротуару, это странно.
JediPhilosopher
13.05.2016 13:50Там на самом деле нет входа. Вход в Максидом там один со стороны парковки.
Иногда такое бывает — почему-то вместо одной тропы образуется две рядом. Не очень понятно почему.
Впрочем поэтому я и не говорю что алгоритм идеально точно подходит для проектирования дорожек, во всяком случае пока. Он скорее позволяет выявить проблемы и показать их проектировщику (то есть сам факт того что люди вот тут будут хотеть ходить напрямую). А конкретное положение дорожки пока придется выбирать человеку.zigzag8312
16.05.2016 17:38Предположу, что это из-за погодных условий:
— если дорожка вытоптана до земли, то после дождя там будет грязь и местами лужи — проще обойти по травке рядом.
— после зимы дорожки тоже смещаются, а старые «версии» не успевают покрыться травой.
JediPhilosopher
13.05.2016 01:33А пешеходы не всегда ходят по прямой. Так как обычно лучше пройти чуть дальше, но по асфальту или уже готовым тропам, чем переть напрямик по грязи.
zigzag8312
13.05.2016 09:49Вчера специально вдумчиво ходил тропами, которые получились естесственным путем. Есть догадка, почему не всегда человек идет к цели по прямой а по дуге — возможно хочется видеть дальнейший путь и возможные опасности чуть раньше, чем возможно дойти до препятствия, за которым следует поворот или слепая зона.
impetus
13.05.2016 11:39у людей есть что-то типа инерции — напр дыру в заборе проходят перпеникулярно, и только мётра через 3 возращаются на «директриссу»
Regis
13.05.2016 14:40Где-то было исследование, что человек обычно может отклониться от тропы к конкретной точке, если между маправлением тропы и целевым направлением (точнее той точкой в прямой видимости, куда вы хотите придти) угол превышает приблизительно 30-35 градусов.
Т.е. если в той конкретной точке, где находится пешеход, цель и тропа расходятся меньше чем на 30 град., то пешеход скорее всего пойдет по тропе. А если больше — высока вероятность того, что срежет.
JediPhilosopher
13.05.2016 17:02Да, в прошлой теме мне уже кидали ссылку. Я правда пока не придумал как это применить. Вообще судя по результатам некоторых симуляций алгоритм поиска пути надо будет менять. А* в некоторых ситуациях рисует может и кратчайшие, но неправдоподобно выглядящие пути.
JediPhilosopher
16.05.2016 14:31В одной из отправленных хабрающерами карт получилось что-то похожее, кстати, почти звезда. Но вообще это вырожденный случай полного графа дорог. когда из каждой точки в каждую напрямик ходят.
guyfawkes
12.05.2016 18:21А исходный код бекенда закрыт и не будет открыт?
JediPhilosopher
12.05.2016 19:36Все открыто — https://bitbucket.org/e_smirnov/antpathplanning
Правда никакого Rocket Science там нет, и в прошлой статье алгоритм работы я подробно описал.
kir_vesp
12.05.2016 19:36А если попробовать сделать начальную расстановку некоторых начальных элементов автоматом, отталкиваясь от карты типа «схема»?
Правда, для этого придётся проводить анализ картинки и разбирать по цвету, но при наложении это может неплохо поспособствовать начальному автозаполнению.
Если решите выложить на github/bitbacket, то люди могли бы с удовольствием подключиться к данной разработке. Меня это заинтересовало по крайней мере.JediPhilosopher
12.05.2016 19:37Вот ссылка на репозиторий https://bitbucket.org/e_smirnov/antpathplanning
Сейчас можно из OSM импортировать данные — здания и дороги. Но вопрос в их правильности и подробности. Если дома еще нормально указаны обычно, то дорожки дворовые уже мало где подробно сделаны.
OlegKrikun
12.05.2016 19:37Всё хорошо, только это проспект Стачек, а не Петергофское шоссе =) шоссе после Жукова начинается =)
wyfinger
12.05.2016 19:37Очень круто!
Id уже рассчитанных карт не простой порядковый номер? добавьте, если можно, возможность просмотреть уже просчитанные чужие карты, вроде ничего секретного в этом нет.JediPhilosopher
12.05.2016 19:38Это MongoDBшный id. А список карт можно увидеть на http://antroadplanner.herokuapp.com/tasks/list
Вообще карт заслали сейчас очень много, но большинство из них бессмысленны. Похоже люди зашли, потыкали в кнопочки наугад и отправили. В итоге куча каких-то случайных полигонов.
4orever
12.05.2016 22:04Как где-то писал Лебедев — чтобы пешеходы не вытаптывали газон, не нужно делать изначально никаких дорожек и тротуаров. Оставить как есть на время. Где появятся тропинки — закатать в асфальт (положить плитку).
JediPhilosopher
12.05.2016 22:34Увы, на такие эксперименты у нас вряд ли пойдут. К тому же это все равно приносит определенное неудобство — ведь первое время, пока дорожки не протопчутся, ходить все равно придется по грязи. А так все было бы уже сразу сделано к моменту появления жильцов.
Moskus
13.05.2016 06:06+1Подобный подход при организации дорожек на территории НИИ приписывали Курчатову, за много лет до того, как кто-то вообще узнал, кто такой Лебедев.
mickvav
12.05.2016 22:11Что-то мне подсказывает, что вы решаете систему нелинейных алгебраических уравнений методом монте-карло+итерация по правой части. Выписать бы её аккуратно и натравить метод Ньютона, например — и можно в браузере решать javascript-ом.
JediPhilosopher
12.05.2016 22:35+2Да то что я делаю и так можно в браузере джаваскриптом сделать, алгоритм-то довольно простой. Тут вопрос не в том что я что-то нереально сложное изобрел, а в том что это похоже раньше было никому не интересно взять и реализовать.
Moskus
13.05.2016 06:09+1Совершенно случайно некоторые дороги в OSM содержат данные о полосности (не все, к большому сожалению) из которых можно позаимствовать ширину. Также, преобразование дорог из осевых линий в полигоны делается построением буфера (стандартная операция любой приличной БД с пространственными функциями) и объединением получившейся геометрии.
JediPhilosopher
13.05.2016 13:51А я так и делаю — в смысле рисую буфер вокруг OSM-ных дорожек. Но толщина этого буфера берется с потолка и может не соответствовать действительности, а это может серьезно влиять на результат.
impetus
13.05.2016 11:49самое частое препятствие в городе для пешеходов (на тротуаре, переходе) — лужа. Часто живут годами, если не десятилетиями. Часто система тропинок продиктована в основном ими. Увы малопрогрнозируемы.
aavezel
13.05.2016 13:40для этого в редакторе, как я понял, и есть непроходимые места: вода. Я так на своей карте «вечную» лужу обозначил
JediPhilosopher
13.05.2016 13:52И как оно, похоже на правду посчиталось? А то уже 400 карт сервис обсчитал (правда там большей частью мусор типа «зашли и потыкали наугад»), а конкретных отзывов пока никто не оставил.
aavezel
17.05.2016 15:52Итак, как и обещал, рассказываю:
1. Из двух тропинок сервис нашел одну. Вторую он не нарисовал. Либо его так напугали кусты, либо есть еще факторы появления там тропинки
2. Он нашел еще 2 тропинки о которых я «не знал» (забыл). Мне пришлось пойти на местность, чтобы понять есть они там или нет. Они там были.
3. Пока гулял, нашел еще одну тропинку — через забор. Люди просто перешагивали через 50 сантиметровый забор, в основном молодежь.
Т.ч. сервис показал интересные результаты на реальном примере. Надо увеличить площадь и позапускать еще несколько раз.JediPhilosopher
17.05.2016 15:59Спасибо за отзыв! А можно ссылку на вашу карту?
Маленькие заборчики стоит рисовать как проходимые препятствия, да, люди через них спокойно шастают.
ChiefPilot
16.05.2016 15:15Тут выше уже писали про «грязь» но как-то не явно. Я лишь хочу подчеркнуть, что часто препятствием является не только лес и кусты, но и просто мокрое место. Его на спутниковых картах может и не быть видно — там та же трава, но там мокро, ноги утопают, ботинки «засасывает» и т. п. Не уверен, что для любых городов, но для того же Санкт-Петербурга это очень актуально. Выходом может быть поиск физической карты местности (с высотами над уровнем моря) и поиск в ней замкнутых низин, которые теоретически могут быть такими мокрыми местами.
JediPhilosopher
16.05.2016 15:26Это нереально. Никакая карта не даст такой точности чтобы лужу на тротуаре/газоне можно было найти. Да и образуются они как правило там где нормальную канализацию не сделали, а это опять же сложно предсказать.
Но чисто по моему опыту это не такое уж частое явление. В большинстве случаев люди спокойно проходят там, где хотят пройти, ведь речь обычно не о заливных лугах, а о десятке метров пустыря с пожухлой травкой между подъездами дома.
shoorick
16.05.2016 22:44В OSM бывают и двумерные дороги — те, что нарисованы полигонами и имеют свойство
area: yes. Кроме того, у дорог в OSM может быть указана ширинаwidthи число полосlanes.JediPhilosopher
16.05.2016 23:39Возможно, но мне такие пока не попадались. Те куски карт что я смотрел этих данных не содержали. Так что рассчитывать на них не приходится.
trolleway
Насколько я понимаю, раз исходные данные берутся с сервисов Яндекс Карт, то конечный результат является производной работой, то есть его создание нарушает лицензионное соглашение Яндекса. Что бы избежать такого нарушения — подложите в редактор карт одну из подложек Openstreetmap.
JediPhilosopher
Ну тут тонкий вопрос. На самом деле исходные данные у яндекса я не беру. Я всего лишь рисую их карту как фон для своего редактора, а рисовать поверх нее вы можете все что угодно. И в симуляции используются только нарисованные пользователем данные.
Поглядел https://yandex.ru/legal/maps_api/ — там ничего не сказано про запрет производных работ. Есть некоторые ограничения (нельзя делать проекты ради дохода, или игровые проекты), но вроде бы ничего такого, подо что мой сервис бы попадал.