Написать алгоритм для Робота-пылесоса, который бы смог пропылесосить замкнутое пространство, при этом робот заранее не знает географию пространства в котором находится. После того, как пространство очищено от мусора Роботу нужно вернуться в исходное состояние. У Робота минимум сенсоров, минимум памяти, поэтому у робота нет возможности точно определять свои географические координаты в пространстве и нет возможности помнить каждую точку пространства.Во время спора меня пытались уверить, что задача нешуточно сложная и что ее еще никому не удалось решить. Хотя мне, казалось, что эта задача не такая уж сложная и уж точно не новая. Мне вспомнилась фича из древней игры "Цивилизация", в которой Колонизатору можно было дать команду "Исследовать территорию", т.е. пройти все затемненные "туманом войны" клетки, что можно интерпретировать, как пропылпесосить всю загрязненную территорию.
Чуть-чуть погуглив я понял, что задача действительно не нова и в различных вариациях решается в современных компьютерных играх с искусственным интеллектом.
Поставленную задачу можно решить итерационным вызовом модифицированного алгоритма A-star.
Для начала решим значительно упрощенную задачу.
- Робот находится в дискретном пространстве. Т.е. все замкнутое пространство можно разделить на конечное число квадратов.
- Робот занимает одну клетку дискретного пространства и видит сенсорами препятствия на одну клетку вокруг себя (включая клетки по диагонали)
- Роботу не нужно возвращаться в исходное состояние
- Алгоритм завершается, после того, как все доступные клетки были очищены от мусора
- Робот движется по пространству четко, без накопления ошибки в пройденном расстоянии и в направлениях движения
Дополнительный материал по теме:
0 коммент.:
Отправить комментарий