roboforum.ru

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

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

К ресурсам я отношу датчики, платформу и т.п.

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

Поэтому попробую разобрать чего сейчас на эту тему напридумывало человечество и прошу всех у кого есть такая информация выкладывать её сюда.

PS: Простейший пример нескольких задач: "Я на 15 минут отбегу, а ты пока уберись в комнате и помешивай суп каждые полчаса".
То есть у нас получается две задачи:
1. Убраться в комнате;
2. Помешивать суп каждые 30 минут;

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

Добавлено спустя 16 минут 11 секунд:
http://www.araa.asn.au/acra/acra2007/pa ... 4final.pdf - Это для множественных роботов (кстати, там наверняка дофига таких задач с ресурсами, в этой области)

http://books.google.ru/books?id=cosenVz ... =1#PPP1,M1 - гугловая превьюшка книги Multiple Abstraction Hierarchies for Mobile Robot Operation in Large Environments

http://intechweb.org/downloadpdf.php?id ... qhslfuii73 - документик Design and implementation of modular software for programming mobile robots

http://www.cs.umanitoba.ca/~jacky/Publi ... _robot.pdf - документик An Intuitive and Flexible Architecture for Intelligent Mobile Robots

http://marie.sourceforge.net/wiki/index.php/Main_Page - Проект MARIE - чего-то для построения робототехнических систем.

Добавлено спустя 19 минут 22 секунды:
Пока скину сюда "поток сознания" возможно это еще один "велосипед"

Ключевые понятия:
1. Ресурс - то чего ограничено;
2. Задача - то чего надо бы выполнить;
3. Райдер:
3.1. постоянный - то чего требует задача чтобы выполнялось всегда между передачей ей активного управления;
3.2. входной - непосредственно перед передачей;
4. Диспетчер - тот кто рулит раздачей ресурсов задачам и т.п.

Добавлено спустя 2 минуты 16 секунд:
Тогда помешивать суп каждые 15 минут может быть повешено задачей по таймеру с входным райдером "находиться на кухне около плиты" + "иметь свободным манипулятор №1".

Добавлено спустя 6 минут 8 секунд:
Требование к ресурсу может быть сформулировано в терминах его состояния (платформа находится в области Х, манипулятор свободен, штанга с видеокамерой поднята и т.п.).

Добавлено спустя 2 минуты 45 секунд:
Каждая задача должна писаться с учетом того, что в любой момент её могут прервать на более важную задачу и вернуться к ней через неизвестное количество времени. Впрочем это не сильно отличается от того, что задача запускается сначала, просто входное состояние в эту задачу может быть более близкое к решению.

Добавлено спустя 19 минут 19 секунд:
В общем получается задачи должны при запуске подписываться на какой-то контракт типа "я тут возьму платформу погонять, обязуюсь вернуть через X минут в радиус 2м от координат (A,B)". Соответственно диспетчер может потребовать с задачи не только подписаться на это, но и расставить серию чек-поинтов так, чтобы если задача ведёт себя неадекватно - забрать у неё управление ресурсом и вернуть его для более важной задачи. Однако, в этом случае, диспетчер должен уметь управлять ресурсами для приведения их в нужное состояние.

В общем можно попробовать разобрать ситуацию на каком-нибудь простом примере:

Пусть есть робот состоящий из:
1. Шасси (пусть колёсное на танковой схеме разворота или гусеничное);
2. Датчики препятствий вокруг (ну или как минимум спереди, тогда шасси круглое);
3. Камера на поворотной платформе на, скажем, штанге торчащей вверх из робота;
4. Манипулятор;

Добавлено спустя 9 минут 29 секунд:
Тогда ресурсов фактически 3:
1. Положение платформы в пространстве;
2. Положение камеры;
3. Положение манипулятора, занятость манипулятора;

Задача уборки в комнате может быть поставлена в основной поток, во вспомогательный поток вешается задача "помешивать суп каждые 30 минут", с райдером "при входе в задачу платформа должна быть максимум в 2м от плиты с супом" + "манипулятор должен быть свободен".

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

интересно. Однако не понятно, что подразумевается под неадекватными действиями других задач?Это типо если суп вышел из своих берегов, а робот помешивает и не подозревает, что суп уже далеко не в кастрюле?

Если все упростить до задач "уборка" и "помешивание супа", то думаю диспетчер должен не просто переключать задачи по таймеру, иначе будет разгром, думаю это и имел в виду ДеД под "неадекватными действиями". Как вариант, надо не переключать задачи, а сначала давать задаче сигнал ( допустим за 5 минут до "помешивания") закончить последние действия до освобождения манипуляторов и потом уже переключать на "помешивание". Конечно, на бумаге все красиво, другое дело реализовать это в жизни...

З.Ы. ну, или я все не так понял и нагородил тут чушь

Задача о СУПЕ:
считаем приоритет 0 - высшим
-------------------------------------------
задача, приоритет 100:
убираться в комнате

задача приоритет 90:
цикл {мешать суп; ждать 30 минут}

задача приоритет 20: (приоритет системный)
цикл {
определить разрешенные местоположения;
если в запрещенном местоположении - пытаться выйти;
ждать 15 сек
}
-------------------------------------------
тогда получится:
- прикладные задачи друг друга не знают и не должны учитывать интересы друг друга
- процесс высокого уровня определяет ограничения/распределяет ресурсы между прикладными задачами, о которых он знает

TrashVigor писал(а):не понятно, что подразумевается под неадекватными действиями других задач?

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

Добавлено спустя 1 минуту 8 секунд:

isk737 писал(а):Как вариант, надо не переключать задачи, а сначала давать задаче сигнал ( допустим за 5 минут до "помешивания") закончить последние действия до освобождения манипуляторов и потом уже переключать на "помешивание".

Всё так поняли, только за 5 минут предупреждать некорректно - см. пример с удалением от кухни в течение 25 минут.

Добавлено спустя 7 минут 56 секунд:

mandigit писал(а):задача, приоритет 100:
убираться в комнате

задача приоритет 90:
цикл {мешать суп; ждать 30 минут}

задача приоритет 20: (приоритет системный)
цикл {
определить разрешенные местоположения;
если в запрещенном местоположении - пытаться выйти;
ждать 15 сек
}

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

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

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

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

2blindman: Ну да, всё примерно так и получается. Я просто и представляю себе, что удобней всего брать готовую систему управления ресурсами из бизнеса/коммерции и транслировать её сюда. Например прокат - когда я беру машину я подписываю договор "когда я её верну, в каком состоянии и т.п. Иначе штрафы и потом мне здесь ничего не дадут". По сути ресурс "шасси" - это такая же машина, которую задачи берут "напрокат", а диспетчер - хитрая программа, которая пытается оптимизировать точки передачи машины между потребителями, чтобы всем было удобней.

Добавлено спустя 1 час 59 секунд:
Кстати, дальше - больше

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

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

Добавлено спустя 9 минут 25 секунд:
Т.е. появляется внутренний элемент мотивации и оценки методов исполнения задач "тугрики" (внутренние деньги) - выживают только лучшие методы, причем лучшие - конкретно тут, а не "где-то там".

Соответственно исполнителю, успешно выполнившему задачу, начисляются "тугрики", провалившему задачу - снимаются. Исполнителю провалившему контракт на ресурсы начисляется штраф. Исполнителю при входе в систему даётся некоторый объем начального "капитала". Исполнитель, объявивший себя банкротом (кончились "тугрики"), убирается из списка кандидатов.

Таким образом мы будем отстреливать неэффективные задачи.

К тому же подход даёт очевидный способ оценки исполнителей по используемым ресурсам - мы можем с исполнителя брать "тугрики" за затребованные им ресурсы. А потом сравнивать эффективность разных исполнителей одной и той же задачи по тому за сколько они готовы выполнить эту задачу.

Добавлено спустя 4 минуты 53 секунды:
Очевидный недостаток подхода - непрозрачность и незащищенность системы от скрытых закладок - т.е. можно будет написать какой-нибудь хороший модуль с закладкой, который захватит всё управление (всеми роботами) в связи со своей оптимальностью, однако в один прекрасный момент за счет накопленного "+" капитала начнет действовать по заложенной в него программе и выполнять совсем не свойственные ему функции. Однако это же сейчас существует на рынке и в принципе ничем критическим не является - вопрос только в размере штрафов за некорректные действия исполнителя. Например, "3 закона робототехники" можно вообще ввести в виде бесконечных штрафов мгновенно вырубающих "исполнителя".

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

Добавлено спустя 36 секунд:
Ничего себе меня понесло

Я смотрю, ты тоже, бодрую, траву куришь

Добавлено спустя 7 минут 21 секунду:
Единственное, что вызывает сомнения, рациональность некоторых задач. Ведь попытка спасти свою "шкуру", подавая на двигатели с механизмами максимального тока, будет оправдана, даже несмотря на возможную поломку.

2Vorral: Ну не лайнтрейсерами же всю жизнь заниматься хотя и его надо тоже сделать, обещал

Подход с мотивированием задач, действительно многообещающая идея.

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

TrashVigor писал(а):Но надо сделать так, что бы задача могла как то себя защитить от
наказания диспетчера.

Это называется не защититься от наказания, а выполнить условия контракта - когда ты в банк несёшь очередной платёж по кредиту, а у тебя башмак разваливается - но ты заходишь в магазин, покупаешь другие башмаки и доходишь до банка и платишь вовремя - это не же не защититься от штрафа, а выполнить условия договора называется?

Да договор.Только для выживания задачи и выполнения договора, ей необходимо совершенствоваться. Допустим наделели ее функцией пылесосить, это первостепенная задача. Повстречала собачку. Как с препятствием бороться она не знает, ее функция пылесосить. Тут нужно сделать вспомогательные диспечеры или модули помощи, они не являются главными просто вносят изменения в задачу для ее реализации. Допустим несколько вспомогательных деспечеров они мега навороченные по определенной тематике, скажем диспетчер припятствий, диспетчер освещенности, дисптчер заряда ботареи ну и т.д.
Диспетчер препятствий знает все ну или почти все о препятствиях с которыми задача может сталкнуться, переберает варианты его устранения формирует подзадачу. Или дапустим батарея разряжается. Задаче незачем знать где розетка находится, зато это знает диспетчер заряда батареи.

TrashVigor писал(а):Да договор.Только для выживания задачи и выполнения договора, ей необходимо совершенствоваться.

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

Не могу представить, как это все будет на машинном уровне выглядеть. если речь идет об ОС.