roboforum.ru

Обдумал немного, получилось:

В самом простом варианте "все по очереди приоритетов":
1. Надо создавать список целей из которых в каждый момент времени выбирается наиболее приоритетная;
2. Надо отдельно создавать список правил и проверять все правила, имеющие больший или равный приоритет с текущей главной целью;

Робот тупой до невозможности

===============================================

Чуть сложнее:

Введем еще понятие стоимости достижения цели (в простейшем варианте - время, которое нужно затратить на выполнение задачи);

Стоимость достижения цели бывает для одной цели из некоторого положения, либо для набора целей, если целей несколько (но тогда учитывается что следующая цель будет достигаться из предыдущего положения).

В более сложном варианте "пытаемся успеть несколько главных целей":
1. В списке целей у каждой кроме приоритета есть крайний срок;
2. Правила просто имеют некоторый приоритет;

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

Как только выполнена какая-то задача, полностью пересматриваем порядок выполнения;

Еще можно дополнить алгоритм "памятью выбранных целей" - т.е. если на предыдущем рассмотрении решили что сейчас нужно делать какие-то операции, то при следующем рассмотрении лучше бы эти операции доделать, а то зря планировали этот вариант.

==============================================

Интересный пример для второго варианта - задача роботу побывать в 50 случайно расставленных по помещению точках, в этом случае при одинаковых приоритетах и крайнем времени выполнения робот будет действовать по "жадному алгоритму", но оптимизируя путь между ближайшими к себе N точками

народ, есть предложение.
Раз уж мы пытаемся алогритм создать, так давайте попробуем всё вышеописанное привести к алгоритмическому виду, только пока без языкового синтаксиса - словесно.

Процедура определение списка следующих N задач и порядка их выполнения:

1. Упорядочим задачи сначала по приоритетам, внутри по времени выполнения, а внутри по стоимости выполнения из текущего положения;
2. Возьмем первые N задач;
3. Переберем все перестановки из этих N задач и для каждой оценим совокупную стоимость выполнения и какие задачи смогут быть выполнены в срок при такой последовательности;
4. Выберем лучшую перестановку по совокупности удачно выполненных задач;
5. Вернем порядок и список задач с моментами начала выполнения как результат своей работы;

При изменении списка задач процедура вызывается заново.

===============================================

Очевидные проблемы такой эвристики:
1. Если нам нужно до завтра выполнить N важных дел и все их можно успеть сделать завтра, а на сегодня с крайним сроком сегодня же есть менее важные дела, то менее важные дела будут загублены.
2. Не ясно как быть с составными задачами, т.е. которые составляют большую задачу и должны выполняться в некой последовательности.

=DeaD= писал(а):Процедура определение списка следующих N задач и порядка их выполнения:

1. Упорядочим задачи сначала по приоритетам, внутри по времени выполнения, а внутри по стоимости выполнения из текущего положения;
2. Возьмем первые N задач;
3. Переберем все перестановки из этих N задач и для каждой оценим совокупную стоимость выполнения и какие задачи смогут быть выполнены в срок при такой последовательности;
4. Выберем лучшую перестановку по совокупности удачно выполненных задач;
5. Вернем порядок и список задач с моментами начала выполнения как результат своей работы;

При изменении списка задач процедура вызывается заново.

===============================================

Очевидные проблемы такой эвристики:
1. Если нам нужно до завтра выполнить N важных дел и все их можно успеть сделать завтра, а на сегодня с крайним сроком сегодня же есть менее важные дела, то менее важные дела будут загублены.
2. Не ясно как быть с составными задачами, т.е. которые составляют большую задачу и должны выполняться в некой последовательности.

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

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

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

=DeaD= писал(а):

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

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

А если препятствие такое, что обойти его нельзя, то система построенная на подобного рода правилах, может не выполнить ни одной из поставленных задач (просто не успеет). Надо подумать над такой ситуацией...

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

Ну вы же, когда идете в магазин за продуктами - не паритесь по поводу "вдруг в городе продукты кончились, или все магазины закрыты сегодня" - а может ведь быть? Вот и тут - если лабиринт такой что не пройти почти всегда, то робот очень быстро этой поймет и сделает соотв. весовой коэфф., иначе будет считать, что почти всегда есть проход.

=DeaD= писал(а):Ну вы же, когда идете в магазин за продуктами - не паритесь по поводу "вдруг в городе продукты кончились, или все магазины закрыты сегодня" - а может ведь быть? Вот и тут - если лабиринт такой что не пройти почти всегда, то робот очень быстро этой поймет и сделает соотв. весовой коэфф., иначе будет считать, что почти всегда есть проход.

Ну ладно поставим вопрос немного по другому.

1. Упорядочим задачи сначала по приоритетам, внутри по времени выполнения, а внутри по стоимости выполнения из текущего положения;

1. Что такое задача? Метод ее представления в вашем случае?
2. Как определяется приоритет (как я понимаю должна быть методология вычисления приоритета, если это число)?
3. Соответственно, как определить стоимость выполнения для задач разного рода? (вообще-то вопрос не совсем корректен, т.к. я не знаю что по-вашему задача...)

В данном случае я описал лишь один из вариантов способа выбора задач.

Виталий писал(а):1. Что такое задача? Метод ее представления в вашем случае?

Метод представления задачи зависит от конкретного проекта. Мне например видимо будет удобен текстовый формат. Синтаксис особого значения не имеет, но могу привести пример.

Виталий писал(а):2. Как определяется приоритет (как я понимаю должна быть методология вычисления приоритета, если это число)?

Не определяется, а назначается в соответствии с правилами, либо явно. Да это число. Например можно назначить приоритет по умолчанию от каждого субъекта, максимальный приоритет, который может назначать каждый субъект и т.п. принципы.

Виталий писал(а):3. Соответственно, как определить стоимость выполнения для задач разного рода? (вообще-то вопрос не совсем корректен, т.к. я не знаю что по-вашему задача...)

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

Мне иногда кажется, что меня пытаются закидать шапками...

Метод представления задачи зависит от конкретного проекта. Мне например видимо будет удобен текстовый формат. Синтаксис особого значения не имеет, но могу привести пример.

Да, пожалуйста, приведите пример...

Не определяется, а назначается в соответствии с правилами, либо явно. Да это число. Например можно назначить приоритет по умолчанию от каждого субъекта, максимальный приоритет, который может назначать каждый субъект и т.п. принципы.

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

...или их линейной комбинацией...

Только линейной?

И еще, объясните мне пожалуйста, что в вашем случае субъект?

P.S. Мне действительно интересен подобный подход к решению проблемы, но не видно никакой конкретики...к сожалению. Правила, еще что-то заоблачное, а вот реального визуализатора - нет...

Виталий писал(а):Мне иногда кажется, что меня пытаются закидать шапками...

Между закидыванием шапками и обсуждением теории пропасть разницы

Виталий писал(а):Да, пожалуйста, приведите пример...

0. СТОЯТЬ;
1. ДВИГАЙСЯ_В_РАЙОН [50,10,60,20];
2. ЗАРЯДИСЬ;
3. ОБНОВИ_КАРТУ [-100,-100]-[100,100];
4. ПРИНЕСИ_ОБЪЕКТ [КРАСНЫЙ_ШАР], РАЙОН [50,60]-[60,70];
5. НАЙДИ_ОБЪЕКТ [ЗЕЛЕНЫЙ_ШАР], РАЙОН [0,0]-[50,50];

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

Приоритет - может определятся явно при получении команды, например я могу дать команду роботу и указать приоритет, а могу не дать, и тогда он должен быть выставлен по умолчанию (соотв. он может быть у каждого субъекта свой "по умолчанию").

Виталий писал(а):

...или их линейной комбинацией...

Только линейной?

Цитируйте полностью там было слово "например".

Виталий писал(а):И еще, объясните мне пожалуйста, что в вашем случае субъект?

Вроде как обычно - тот, кто может давать команды роботу.

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

Потому что сначала надо обсудить и перетереть алгоритм, а потом реализовывать. Конкретика - это уже с объявлениями конкретных массивов и списком статусов - я до такого опускаться буду только в своей конкретной программе. До этого мне важен принцип.

PS: Сразу предупреждаю - моя конкретика будет работать на PC, поэтому я буду использовать его огромные вычислительные мощности. Однако думаю принципы подойдут и для МК.

Между закидыванием шапками и обсуждением теории пропасть разницы

Она сокращается, до размеров трещины в асфальте, как только теоретики начинают препираться =)

...
ДВИГАЙСЯ_В_РАЙОН [50,10,60,20];
...

На думать данная команда разбивается на ряд более мелких (элементарных) самим роботом (не будем уточнять каким образом). И соответственно сам робот расставляет приоритеты я так понимаю? Если я понимаю, то как он это будет делать? Если я понимаю неправильно, то где по вашему робот-то?

Вроде как обычно - тот, кто может давать команды роботу.

Давайте будем называть это управляющим устройством...все-таки субъект это
немного другое.

Потому что сначала надо обсудить и перетереть алгоритм, а потом реализовывать. Конкретика - это уже с объявлениями конкретных массивов и списком статусов - я до такого опускаться буду только в своей конкретной программе. До этого мне важен принцип.

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

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

У меня это будет разбиваться уже внутри схемы выполнения команды и приоритет будет только у всей команды целиком, но можно рассматривать и другие варианты. Что значит "где по вашему робот-то"?

Виталий писал(а):Давайте будем называть это управляющим устройством...все-таки субъект это немного другое.

Не я полез в философию Толковый словарь, "СУБЪЕКТ" - 5. В грамматике: семантическая категория со значением производителя действия или носителя состояния.
Если хотите могу называть управляющим устройством.

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

1. Я имею общий опыт программирования в достаточном объеме и достаточного уровня, в т.ч. разумеется успешного решения задач гораздо более сложных, чем создание формочек;
2. Мне интересна тема создания алгоритмов для управления роботом, уровня существенно выше "стукнулся => отъехал назад";
3. Я изучаю темы связанные с этими алгоритмами, читаю статьи всяких MIT и ему подобных на эти темы;
4. Я написал софт для управления 4х-ногим роботом с моделированием его перемещения по поверхности и прямой и обратной кинематикой + тупые пара команд типа идти вперед и повернуться;
5. В данный момент я собираю колесную базу для исследования алгоритмов составления карты (пока не заморачиваюсь на 4-хногого робота, т.к. запарок много, а темных мест, которые я не уверен что преодолею, типа работы с 2мя вебкамерами сразу, до кучи). Схемы управления всей фигней уже испытаны, сегодня куплю еще пару сервов для управления камерой.

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

Так я ел устриц?

PS: А на основе чего Вы хотите перетирать эту тему?

У меня это будет разбиваться уже внутри схемы выполнения команды и приоритет будет только у всей команды целиком, но можно рассматривать и другие варианты. Что значит "где по вашему робот-то"?

Просто если вы разбивате команду, то получаете, опять таки задачу расстановки приоритетов, но теперь уже роботом...посему очень интересен способ этой самой расстановки, а заодно и определения приоритетов.
"где по вашему робот-то" - если вы будете давать роботу элементарные команды самостоятельно анализируя его состояния и расставляя приоритета...ну далше понятно. Суть вопрос исчерпан.

Не я полез в философию  Толковый словарь, "СУБЪЕКТ" - 5. В грамматике: семантическая категория со значением производителя действия или носителя состояния.

Я тоже не лез.. Просто теперь посмотрим
"Вроде как обычно - тот, кто может давать команды роботу." и "семантическая категория со значением производителя действия или носителя состояния" немного разные понятия, но вобщем разобрались...

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

Не будем злословить на эту тему...но мне непонятно, достаточным для чего?

2. Мне интересна тема создания алгоритмов для управления роботом, уровня существенно выше "стукнулся => отъехал назад";

По большому счету, если говорить об алгоритмах объезда (отъезда) от препятствий на примитивных ИК датчиках, то все сводится именно к этому.

4. Я написал софт для управления 4х-ногим роботом с моделированием его перемещения по поверхности и прямой и обратной кинематикой + тупые пара команд типа идти вперед и повернуться;

А проверили работает или нет на живой модели?

Так я ел устриц?

Не могу судить...

PS: А на основе чего Вы хотите перетирать эту тему?

Для начала, на алгоритме отъезда от препятствий, потому как такое понятие как управление роботом слишком обширно ИМХО.

 Горячие финские Парни