roboforum.ru

Технический форум по робототехнике.

Энциклопедия по робототехнике - Поиск пути на карте (обсужд.)

Вопросы не попавшие в другие категории.

Энциклопедия по робототехнике - Поиск пути на карте (обсужд.)

Сообщение =DeaD= » 15 дек 2007, 13:23

Guriy писал(а):возникли вопросы:
-Алгоритмы будут помещаться как сканы с бумаги?
-В каком виде алгоритмы нужно делать? На руссом алгоритмическом, блок-схемами, UML etc.?
а то кто-то код выложит по незнанию....

Есть классические подходы к изложению алгоритмов, например, как в общепризнанной книжке Кормена - "Алгоритмы и структуры данных" (http://www.ozon.ru/context/detail/id/83808/). Там используется условный язык в котором описываются все алгоритмы. Вполне можно привести в википедии описание этого языка и все примеры писать на нем. А вообще по опыту могу сказать, что можно легко приводить описания алгоритмов на любом общепризнанном языке (С++, Паскаль, Бейсик), если будут нормальные комменты и код с именами переменных - читабельный, то кому надо, тот без особых проблем разберется. А если комменты будут убогие и код написанный "лишь бы запустился", то никакой правильный язык или диаграммы не помогут.

Guriy писал(а):имхо нужно просто добавить подразделы в программирование, типа:

Программирование:
- Алгоритмы и структуры данных
- Программная реализация

а алгоритмы выкинуть с верхнего уровня

Ну-ну, еще скажите, что софт и железо оставим на верхнем уровне... предлагаю прекратить этот бессмысленный спор :).

Добавлено спустя 16 часов 38 минут 11 секунд:
Вот! Первая серьезная статья по алгоритмам написана и выложена :)

[[Перемещение робота в нужную точку карты]]

Прошу заценить.

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

Добавлено спустя 1 минуту 22 секунды:
Еще я так и не понял с выносом справочника решений в левое меню или вообще куда-то чтобы было удобно пользоваться. Вариант со вставкой во все страницы справочника в правое меню страниц содержания - не предлагать. Таблицы тогда нормально не влезают.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Энциклопедия по робототехнике

Сообщение Guriy » 15 дек 2007, 14:22

=DeaD= писал(а):Прошу заценить.

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


Вот этот язык и назывался в мое время "русским алгоритмическим"
Аватара пользователя
Guriy
 
Сообщения: 122
Зарегистрирован: 13 окт 2007, 14:07
Откуда: Украина, Киев

Re: Энциклопедия по робототехнике

Сообщение Digit » 15 дек 2007, 14:37

2 =DeaD=
1. Заценить смогу только в понедельник.
2. Навигацию по разделам закончу на неделе.
3. Дай все ж определение разделу "алгоритмы". Вернее, не определение, а описание раздела, краткую аннотацию. Для остальных разделов видимо аннотацией будет то, что вы с АВР123 понаписали?
злой полицейский
Аватара пользователя
Digit
 
Сообщения: 3339
Зарегистрирован: 27 ноя 2004, 00:42
Откуда: совсем Москва
ФИО: Григорий

Re: Энциклопедия по робототехнике

Сообщение =DeaD= » 15 дек 2007, 15:00

Digit писал(а):Дай все ж определение разделу "алгоритмы". Вернее, не определение, а описание раздела, краткую аннотацию. Для остальных разделов видимо аннотацией будет то, что вы с АВР123 понаписали?

А вообще есть сейчас смысл вводить эти аннотации? Есть человек заблудившийся в этой структуре, он не один? :)

Если уверены, что надо - давайте сделаем :)

Алгоритмы и структуры данных - методы решения различных расчетных задач, не привязанные к конкретным средствам разработки и языкам программирования.

Программирование - особенности разработки программ на различных платформах и в различных средах разработки, включая особенности программирования портов ввода-вывода.

И что с АВР123 написали - можно использовать как аннотации.

Остаётся "вычислительная сеть робота" - различные вычислительные модули (процессоры на материнских платах, контроллеры и микроконтроллеры) и способы их подключения друг к другу.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Энциклопедия по робототехнике

Сообщение Digit » 15 дек 2007, 16:42

=DeaD= писал(а):Если уверены, что надо - давайте сделаем :)


:D Ых, мы общаемся на "ты" ;)
Я думаю, что надо. Когда будут аннотации у разделов - меньше будет вопросов у тех, кто занимается данным проектом. Пока абсолютная ясность насчет того, что где должно лежать и в каком виде, есть только у тебя! :wink: Так что в целях внесения ясности аннотации и надо ввести.
злой полицейский
Аватара пользователя
Digit
 
Сообщения: 3339
Зарегистрирован: 27 ноя 2004, 00:42
Откуда: совсем Москва
ФИО: Григорий

Re: Энциклопедия по робототехнике

Сообщение =DeaD= » 15 дек 2007, 16:45

Digit писал(а):
=DeaD= писал(а):Если уверены, что надо - давайте сделаем :)

:D Ых, мы общаемся на "ты" ;)

:idea:

Digit писал(а):Я думаю, что надо. Когда будут аннотации у разделов - меньше будет вопросов у тех, кто занимается данным проектом. Пока абсолютная ясность насчет того, что где должно лежать и в каком виде, есть только у тебя! :wink: Так что в целях внесения ясности аннотации и надо ввести.

Засчитывается :)
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Энциклопедия по робототехнике

Сообщение Digit » 16 дек 2007, 01:11

Добавил аннотации вроде близко к вашим, но с вольностями. Почитайте.

И может оформление разделов сделать, как на [[главной]] странице вики "добро пожаловать" сделано? Ну, чтоб каждый раздел в своем "окошке" синеньком?
злой полицейский
Аватара пользователя
Digit
 
Сообщения: 3339
Зарегистрирован: 27 ноя 2004, 00:42
Откуда: совсем Москва
ФИО: Григорий

Re: Энциклопедия по робототехнике

Сообщение =DeaD= » 16 дек 2007, 09:22

Digit писал(а):Добавил аннотации вроде близко к вашим, но с вольностями. Почитайте.

И может оформление разделов сделать, как на [[главной]] странице вики "добро пожаловать" сделано? Ну, чтоб каждый раздел в своем "окошке" синеньком?

Да, вроде неплохо должно получиться, как раз 6 групп в 2 колонки сделать, попробовать надо - будет время сегодня - попробую. И картинки еще подцепить, типа в алгоритмах - блок схема, в программировании - кусок с++ кода, в исполнительных устройствах - двигатели и т.п. :)
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Энциклопедия по робототехнике

Сообщение Digit » 17 дек 2007, 11:03

Ок. Давай я в понедельник сделаю.

Добавлено спустя 10 часов 42 минуты 21 секунду:
=DeaD= писал(а):Вот! Первая серьезная статья по алгоритмам написана и выложена :)

[[Перемещение робота в нужную точку карты]]

Прошу заценить.


Заценил.
То ли из-за того, что читал посреди ночи, то ли написано так, но алгоритм Дейкстры, хоть я о нем и имею представление, не понял :pardon: Не вполне понятно написано, как мне кажется. Возможно, имеет смысл вначале рассмотреть упрощенный случай - например алгоритм А* - а потом сформулировать уже алгоритм Дейкстры в общем виде?
И еще. Иллюстраций мало :) Сейчас повторно статью перечитаю и нарисую какие-схемки для наглядности.

А,еще одну штуку вспомнил! Про переход от векторного пространства к взвешенному графу: не понятно, каким образом этот переход осуществляется. Подраздел называется " Переход к задаче поиска пути во взвешенном графе", но при этом для случая векторной карты данный переход не раскрыт. Непорядок.
злой полицейский
Аватара пользователя
Digit
 
Сообщения: 3339
Зарегистрирован: 27 ноя 2004, 00:42
Откуда: совсем Москва
ФИО: Григорий

Re: Энциклопедия по робототехнике

Сообщение =DeaD= » 17 дек 2007, 11:18

Digit писал(а):Ок. Давай я в понедельник сделаю.

Вижу начал делать :) а я закончил и картинок подцепил. Теперь просто конфетка! => [[Справочник решений]] <=

Digit писал(а):Заценил.
То ли из-за того, что читал посреди ночи, то ли написано так, но алгоритм Дейкстры, хоть я о нем и имею представление, не понял :pardon: Не вполне понятно написано, как мне кажется. Возможно, имеет смысл вначале рассмотреть упрощенный случай - например алгоритм А* - а потом сформулировать уже алгоритм Дейкстры в общем виде?
И еще. Иллюстраций мало :) Сейчас повторно статью перечитаю и нарисую какие-схемки для наглядности.

Иллюстраций вообще вроде нет :) не занимался еще. А пожалуй надо. Дейкстру - да, сумбурно наверное получилось. Но и тема не простая :)

Digit писал(а):А,еще одну штуку вспомнил! Про переход от векторного пространства к взвешенному графу: не понятно, каким образом этот переход осуществляется. Подраздел называется " Переход к задаче поиска пути во взвешенном графе", но при этом для случая векторной карты данный переход не раскрыт. Непорядок.

Вот же на той же странице раздел есть - "Построение графа допустимых путей для векторной карты". Там всё написано, правда без иллюстраций тоже фиг поймешь :)
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Энциклопедия по робототехнике

Сообщение Digit » 17 дек 2007, 11:28

=DeaD= писал(а):Вижу начал делать :) а я закончил и картинок подцепил. Теперь просто конфетка! => [[Справочник решений]] <=

Ага, супер! :)

=DeaD= писал(а):Вот же на той же странице раздел есть - "Построение графа допустимых путей для векторной карты". Там всё написано, правда без иллюстраций тоже фиг поймешь :)

Блин, я ступил :) Читал еще в ночь с субботы, запомнил, что с векторной косяк, а сейчас сгоряча написал... :oops:
В общем, если опять ничего не путаю, там не дается метода составления графа. В этом разделе есть метод выделения бесконечного множества вершин, которые могут быть вершинами графа. Но поиск на бесконечном графе - это нонсенс! :) А как перейти от бесконечного множества к конечному - не показано... Разве что использовать в качестве таких вершин вершины многоугольников, описанных вокруг препятствий на расстоянии SafeDistance... Но тогда маршрут не оптимален по цене, а робот получается зашуганным и "жмется к стенкам" :D
злой полицейский
Аватара пользователя
Digit
 
Сообщения: 3339
Зарегистрирован: 27 ноя 2004, 00:42
Откуда: совсем Москва
ФИО: Григорий

Re: Энциклопедия по робототехнике

Сообщение =DeaD= » 17 дек 2007, 12:39

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

Бесконечного то почему??? Мы же каждое препятствие обводим многоугольником, просто количество вершин в многоугольнике можем варьировать балансируя между производительностью и точностью. А конечное число (препятствий конечное число - иначе это не к нам :)) конечных чисел (каждый многоугольник вокруг препятствия имеет конечное число вершин) + 2 вершины (старт+финиш) = конечное число.

Digit писал(а):Но поиск на бесконечном графе - это нонсенс! :) А как перейти от бесконечного множества к конечному - не показано... Разве что использовать в качестве таких вершин вершины многоугольников, описанных вокруг препятствий на расстоянии SafeDistance... Но тогда маршрут не оптимален по цене, а робот получается зашуганным и "жмется к стенкам" :D

А я этой и имел в виду :) про вершины препятствий. А вот про зашуганного робота - вранье, он не жмется к стенкам, а ломится напрямую, где можно. А где нельзя - не "жмется к стенкам", а "технично огибает препятствия". Можешь убедиться в этом построив маршрут по моему алгоритму и попробовав найти другой, более оптимальный маршрут.
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Энциклопедия по робототехнике

Сообщение Digit » 17 дек 2007, 12:43

В статейке нарисовал немного картинок. Продолжаю рисование :)
Счас построю по твоему алгоритму и посмотрим :wink:
злой полицейский
Аватара пользователя
Digit
 
Сообщения: 3339
Зарегистрирован: 27 ноя 2004, 00:42
Откуда: совсем Москва
ФИО: Григорий

Re: Энциклопедия по робототехнике

Сообщение =DeaD= » 17 дек 2007, 12:51

=DeaD= писал(а):
Digit писал(а):Но поиск на бесконечном графе - это нонсенс! :) А как перейти от бесконечного множества к конечному - не показано... Разве что использовать в качестве таких вершин вершины многоугольников, описанных вокруг препятствий на расстоянии SafeDistance... Но тогда маршрут не оптимален по цене, а робот получается зашуганным и "жмется к стенкам" :D

А я этой и имел в виду :)

Кстати, я поправил там слегка, теперь понятнее написано?

Добавлено спустя 6 минут 35 секунд:
Digit писал(а):алгоритм Дейкстры, хоть я о нем и имею представление, не понял :pardon: Не вполне понятно написано, как мне кажется.

Может вообще не париться, да в википедию сослаться общую? http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры

Как думаешь? Или оттуда стырить описалово?
Проект [[Open Robotics]] - Универсальные модули для построения роботов
Аватара пользователя
=DeaD=
 
Сообщения: 24218
Зарегистрирован: 06 окт 2004, 18:01
Откуда: Ебург
прог. языки: C++ / PHP / 1C
ФИО: Антон Ботов

Re: Энциклопедия по робототехнике

Сообщение Digit » 17 дек 2007, 14:55

В общем, проверил векторный вариант на листике :) робот поедет достаточно прямо... Но все-таки он не в состоянии проехать между двумя препятствиями по центру - он будет прижиматься к одному из препятствий. А еще решение задачи триангуляции не в статье не описано :) Мы ж не можем сделать полносвязный граф - надо проверять пересечение ребер графа и препятствий... В общем, как-то так :)

Добавлено спустя 2 минуты 49 секунд:
=DeaD= писал(а):Может вообще не париться, да в википедию сослаться общую? http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры

Как думаешь? Или оттуда стырить описалово?


Я в примечание (внизу) вставил ссылку и на Дейкстру и на его алгоритм... Не знаю даже. Может в общих словах, так сказать "для чайников", сделать описание, а за подробностями посылать в Вики?

Добавлено спустя 6 минут 51 секунду:
Рисунков достаточно?

Добавлено спустя 29 минут 56 секунд:
А зачем обводить препятствия, представленные в виде прямоугольников, прямоугольниками со скругленными углами? Мы ж по-танковски поворачиваем и на время поворота забили... :unknown:

Добавлено спустя 5 минут 48 секунд:
Вики писал(а):После построения такой карты границ препятствий можно легко составить граф допустимых путей на базе вершин многоугольников из только что построенной карты и начальной + конечной вершин. При этом, конечно, каждое ребро графа допустимо, если не пересекает какой-либо границы препятствия.

Вот к вопросу о триангуляции, о которой я говорил выше... Надо привести алгоритм, позволяющий построить граф, удовлетворяющий условиям из цитаты.

Добавлено спустя 1 час 9 минут 4 секунды:
...в общем для иллюстрации "на пальцах" засунул туда алгоритм А*. Пойдет? Или вообще теперь огромная статья - никто читать не будет? :)
злой полицейский
Аватара пользователя
Digit
 
Сообщения: 3339
Зарегистрирован: 27 ноя 2004, 00:42
Откуда: совсем Москва
ФИО: Григорий

След.

Вернуться в Обо всём

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 0

cron