Приложение для "Бегущего города" (проект)

Ментор	Попов Олег
Учебный семестр	Весна 2016
Учебный курс	1-й курс
Максимальное количество студентов, выбравших проект: 3

Что это за проект?

Одним из наиболее популярных соревнований по городскому ориентированию является "Бегущий город" ((http://runcity.org)). Проходят они в общих чертах так: есть несколько этапов, в начале этапа выдаётся список адресов КП (задание загадками в рамках проекта не рассматриваем), которые надо посетить на этом этапе, и адрес финиша этапа, на котором даётся задание на следующий этап. На каждом КП надо рассмотреть что=то на местности и записать увиденное. КП можно посетить в любом порядке, и первая задача участника — найти КП на карте и определить, в каком порядке их проходить. Хочется сделать приложение, по возможности автоматизирующее эту задачу.

Чтобы быть полезным, это приложение должно работать на каком-то устройстве, которое участник носит с собой, то есть разумной платформой будут Android, iOS или Windows 10. Мой выбор — Windows 10, но можно на свой страх и риск работать с какой-то другой платформой.

Итак, на вход это приложение получает фото листа с заданием (+2 балла, если научите его работать прямо с камерой устройства). Для начала надо распознать текст на этом изображении, выделить из него адреса КП и сохранить их список в каком-нибудь распространённом формате данных — я предлагаю json. Для распознавания под Windows 10 есть встроенная библиотека, под другими платформами можно попробовать Tesseract или какой-нибудь веб-сервис на его основе, скажем, ocrwebservice.com, ocr.a9t9.com или onlineocr.net. Выделять адреса из текста можно либо ещё на картинке по размеру шрифта в строках, либо по всяким словам-маркерам типа "ул." ((https://en.wikipedia.org/wiki/Named-entity_recognition Named entity recognition)).

После того как список адресов получен, нужно отобразить его как точки на картах. Можете выбрать карты на свой вкус, скажем, одни из maps.yandex.ru, maps.me, maps.google.com, maps.here.com, www.openstreetmap.org, почитав документацию на их API (+1 балл за поддержку 3 карт из списка). После этого хорошо дать пользователю возможность поправитть эти точки, скажем, передвинуть точку к конкретному подъезду дома, но в минимальном варианте можно обойтись без этого. Затем нужно через API маршрутизации померить расстояния между этими точками по допустимым маршрутам. В "Бегущем городе" есть разные категории, скажем, пешая, велосипедная, автомобильная, общественный транспорт. Если API выбранных вами карт поддерживает разные способы маршрутизации, то следует предоставить пользователю выбор.

Получив расстояния, следует построить кратчайший маршрут от начала до конца этапа, проходящий через все КП. Это вычислительно сложная задача (задача коммивояжёра), для которой, как я понимаю, нет методов сильно лучше полного перебора, но на этапе около 10 КП, так что перебор должен быть осуществим.

Бонус: в "Бегущем городе" также есть бонусные КП, список которых выдаётся на старте. В качестве бонуса можно научиться рисовать на карте также и их, а также учитывать их в построении маршрутов. Здесь нужно будет принимать решение, стоит ли посещать бонусный КП на данном этапе или стоит отложить его до одного из следующих, так как он очень далеко от всех КП данного этапа. Видимо, решение стоит принимать на основании какого-нибудь несложного классификатора из машинного обучения, используя в качестве факторов расстояния между КП этапа, а также между КП этапа и бонусным КП.

Чему вы научитесь?

Вы научитесь работать с API веб-сервисов и слегка ознакомитесь со структурой веб-страницы и, видимо, с языком Javascript, потому что без него с API карт никак. А также собирать умные приложения из готовых блоков. И немножко поделаем пользовательские интерфейсы.

Какие начальные требования?

Готовность читать англоязычную документацию и подбирать инструменты под задачу.

Какие будут использоваться технологии?

API карт, какие-либо библиотеки или сервисы OCR, машинное обучение.

Направления развития

Довольно много рюшечек уже описано вышне и ниже. Ещё можно попытаться сделать маршрутизацию на общественном транспорте с учётом его расписания (т.е. 10 минут на КП и беги на электричку). Ещё хорошо научиться рисовать точки на закешированных картах в отсутствие интернета (под Windows 10 встроенное приложение работает с here maps, например), в том числе посмотреть на возможности 2gis.

Критерии оценки

4-5 баллов: либо этап от фото до json'а, либо этап от json'а до маршрута. 6 баллов: от фото до json'а + нанести точки на карту как они есть; либо от json'а до маршрута + выбор типа маршрутизации + возможность поправить точки перед маршрутизацией. 8 баллов: оба этапа из категории "4-5 баллов". +2 балла: на входе работать с камерой, а не с готовым фото. +1 балл: выбор типа маршрутизации +1 балл: возможность поправить точки (в браузере) перед маршрутизацией. +1 балл: автоматическое определение типа маршрутизации по тексту задания (категории "Бегущего города"). +1 балл: поддержать 3 сервиса карт из списка. +1 балл: отображать бонусные КП на карте. +2 балла: учитывать бонусные КП при маршрутизации.

Ориентировочное расписание занятий

ПН 11-13, ВТ недоступен, СР 11-15, ЧТ недоступен, ПТ недоступен, СБ 11-15