«Четверг на Динамо по выбору» или «Может ли робот сделать выбор оптимального маршрута не хуже человека?»

В этот четверг, как и в любой другой летний четверг, все идем на ориентирование!

В этот раз старт в 19:00 на изгибе левой линии освещенной асфальтированной трассы. Начало регистрации в 18:30 на лыжной базе «Лыжная».

Выкладываем РЕЗУЛЬТАТЫ старта 2012.08.16.

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

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

22 мыслей о “«Четверг на Динамо по выбору» или «Может ли робот сделать выбор оптимального маршрута не хуже человека?»”

  1. Результаты выложены.

    Надя, спасибо большое за такую активную дистанцию! 36 КП за час, это сильно! На старте все были в шоке сложностью постановки задачи, плюс надо с собой карандаш тащить.. Но получилось весело, а главное очень полезно. Теперь знаю каждую «дыру» в районе освещенки. Раньше туда никто даже и не догадывался ставить КП-шки:) получилось образцовое парковое ориентирование.

    Отдельно надо отметить скорость подсчета результатов — Надя скинула мне файл с результатами, с прописанными вариантами и отсечками по кругам в пол первого ночи! Вот это фанатизм! в хорошем смысле этого слова:)

  2. После такой жесткой головоломки по выбору последовательности взятия КП, мне в голову пришла идея такого вот онлайн сервиса «Расчитать оптимальный маршрут по выбору»:
    1. Человек загружает карту.
    2. Указывает местоположение старта, всех КП и возможно финиша.
    3. Дистанция загружается на сервер и обрабатывается:
    — Вычисляется дистанция на каждом отрезке (по азимуту).
    — Вычисляется сложность прохождения леса (рядом с линией найти тропы, поле, лес, зеленку, болота, ручьи).
    — Определить наличие спусков и подъемов по сечениям рельефов (самая сложная задача).
    — На основе этих показателей расчитать примерное время прохождения отрезка (некий коэфициент).
    — Вычислить оптимальный маршрут: «по азимуту» и «по азимуту с учетом местности».
    4. Отобразить оптимальные пути на карте.

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

  3. Костромин Александр

    Есть программка, которая вычисляет наилучший вариант на выборе. На Московском Меридиане надо поглядеть. Окад 9 вычисляет длину дистанции в сплите на выборе.
    «— Вычисляется сложность прохождения леса (рядом с линией найти тропы, поле, лес, зеленку, болота, ручьи).»-это сделает только человек.

  4. В том то и смысл — попробовать научить программу распознавать, где тропинка, где лес, где зеленка, а где болото. Гипотетически это возможно, но в действительности очень сложно такое запрограммировать:(

    Хотелось бы посмотреть программку с Мос Меридиана — я что-то не нашел.

  5. Спасибо большое за дистанцию, а то давно уже думать нормально не приходилось!

  6. а зачем учить программу распознавать лес, тропинку …такие программы существуют, нам нужен только цветоделенный растр (к примеру по каналам RGB) после чего мы указываем цвет и диапазон в котором он может меняться и начинаем поиск, в результате чего у нас получаются тематические выборки, подобным образом происходит автоматическая векторизация, в свою очередь с векторными объектами можно выполнять разного типа запросы — атрибутивные пространственные и т.д. проще говоря выполнять сетевой анализ — задачу коммивояжёра ни кто не отменял…и это все было реализовано в 80-х годах прошлого века..
    сейчас же подобные задачи решаются на алгоритмах «компьютерного зрения» когда участвует не цвет а поле яркости, можешь посмотреть алгоритмы — Sift ,Surf ,Bundle adjustment, Dense stereo — они новые, они известны и их можно запрограммировать..
    что касается рельефа — в свободном доступе есть данные SRTM — радиометрического зондирования Земли (матрица высот на всю Землю по участкам) правда точность у нее не более 0,5-1 м. хотя официально заверяют 18 см. — п****т , но вам этого должно хватить, если нет то векторизуете существующие карты и делаете из них матрицу высот — grid, либо какую-то полигональную модель типа tin

  7. Александр К.

    Дима, не усложняй.
    У нас проблема с качественными картами, а …
    больше заинтересовали данные SRTM, дай ссылочку, а лучше готовый вектор на какой нибудь район.

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

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

    Особо сложно мне представляется решение задачи вроде «как оббегать болото» или «зачем подниматься на холм и спускаться, если его можно оббежать лишь немного увеличив путь». С такими задачами с легкостью справится человек, даже из группы МЖ-12:) А запрограммировать такой анализ — на данный момент под силу может быть только какому-нибудь НИИ военной направленности…

    Мне на почту еще и второй Дима, который Шевелев написал по данному вопросу:

    Я думаю это можно реализовать! На первом этапе оцифровать и перевести в векторный формат растр, далее уже имея вектор можно каждый объект разделять и присваивать какой-либо атрибут., инфо, т.е. часть тропинки труднопроходимая имеет определенных коэфициент, другая более лучшие условия другой.Это линейные объекты. Необходимо будет для каждой карты производить замеры времени для различных вариантов прохождения, а потом присваивать коэффициенты для каждого объекта или части объекта. Это в принципе реализуется для карт города, когда навигатор определяет лучший маршрут в зависимости от времени суток, загруженности дорог, условий дорожного покрытия. Это можно сделать в программе ArcGis, сложнее будет соединить информацию с линейного объекта и информацию по рельефу. Модель можно попробовать сделать, но как это в дальнейшем выложить на сервер не знаю. В программе arcgis это реализуемо.

    У нас тут уже набирается целое НИИ:)

    Хочу еще сказать по поводу автоматизации картографии. В поисках решений описанной выше задачи, я наткнулся на последнюю разработку от создателя RouteGadget: http://www.routegadget.net/karttapullautin/

    Этот комплекс из Ocad, OL Laser (http://oapp.se/Applikationer/OL_Laser.html) и собственно этой вот программы, позволяет распознавать ариальные лазерные снимки местности, которые дают карту высот, и, на их базе, плюс снимков со спутника, плюс данных из открытых источников, создавать точнейшие карты для ориентирования практически полностью автоматически! Фантастика!

    Вот такая карта получается практически полностью автоматически, без полевых работ: https://picasaweb.google.com/102448094798715080606/Misc#5774663704865676130

    Но у них, там в Финляндии — совсем другая основа для таких разработок. Как минимум, есть картографическая база с точнейшим рельефом и объектами. Например, для местности приведенной выше карты: http://kansalaisen.karttapaikka.fi/kartanhaku/osoitehaku.html?x=509657&y=7629516&srs=EPSG:3067&text=location&scale=40000&action=link&mode=&lang=en

    Карты высот, построенные на основе ИК-съемки, действительно доступны для всего земного шара. Но проблема в том, что в разных районах — разная точность. Я когда-то качал такие снимки с сайта NASA, но там точность по-моему была 30 метров.

  9. Костромин Александр

    Я не соглашусь с мнением «НИИ»…
    Анализ пути на местности очень субъективное мнение.
    Даже для одного ориентировщика, в зависимости от его подготовленности, пути движение на КП будут разные.
    Я готов физически-свободно буду сокращать путь через холмы.
    Я не готов технически-пойду оббегать по линейным объектам.
    И наоборот.

  10. Костромин Александр

    Дима, программы ГИС у меня нет. Погрешность 6-8 метров.
    Хочется увидеть высоты наших карт.

  11. я не предлагаю изобрести велосипед, я просто предлагаю вам им воспользоваться, все о чем я писал уже реализовано и для решения любой задачи необходимо просто подобрать необходимое ПО..
    что касается оптимального пути Дима Шевелев прав, любой векторной информации можно присвоить атрибутивную и заняться геоинформационным анализом — это проще, разработать систему коэффициентов для этого возможно+ее экспериментально можно проверить на полигоне, если правда это система уже не разработана и вообще необходимо привлекать больше народу из других регионов для подобных целей…
    Шурик, мне нужно знать какой файл тебе надо открыть и посмотреть (название его) и в каком формате ты хочешь это увидеть?

  12. Костромин Александр

    Пока некогда копаться с прогами, работы много.
    Есть возможность наложить высоты на космоснимок?
    Например Динамо.

  13. Надежда Рудакова

    Дискуссия очень интересная. Мы в свое время (80-ые годы) в сборной СССР вручную просчитывали оптимальные пути по карте и на местности, с учетом проходимости дорог, растительности, склонов и пр. Анализировали каждый перегон и неоднократно его пробегали разными вариантами. Было интересно. Сейчас если будет такая «умная» компьютерная программа — будет интересно сравнить возможности человека и «ум» робота. Дерзайте, а мы потом на детях проэкспериментирум. Успехов!!!

  14. Надежда Рудакова

    Саша Костромин! Как насчет этого Четверга в Затоне? Подвести итоги летнего сезона Четвергов и построить планы на осень. Предлагайте. Мы поможем организовать.

  15. Ну, как будем проводить этот четверг? Вообще, хотелось бы уточнить программу на сентябрь-октябрь и добавить события в календарь с заявкой, чтобы все могли заранее спланировать свои четверги и выходные. По плану в календаре следующие старты:

    — август-сентябрь — Первенство СО «Динамо» МЖ-21

    — 19 сентября — Традиционные массовые соревнования школьников по СО бегом «Первый старт» МЖ-10,12,14, Парк им. С.М. Кирова

    — 23 сентября — Республиканские соревнования по СО бегом «Золотая осень» МЖ-12,14,16,18,20,21, Сыктывкар

    — 6-7 октября — Первенство РК среди учащихся по СО бегом МЖ-12,14,16,18,20, Коччойяг

    — 21 октября — Закрытие летнего сезона «Осенний марафон и эстафеты» Кубок клубов СО РК, Сыктывкар

    — 28 октября — Открытая матчевая встреча учащихся г. Сыктывкара по СО бегом, пгт. Краснозатонский

    Кто обладает более подробной информацией, сбрасывайте мне данные и положения — я опубликую…

  16. Алексей Козлов

    Что с четвергом? Видать все гуру поставили по разу и больше не тянет.
    Могу сам поставить дистанцию на Динамо. Необходимы только карты.

Оставьте комментарий

Ваш адрес email не будет опубликован.