roboforum.ru

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

Есть лаба по ИИ - симуляция миры пылесоса со следующими входящими данными:

пылесос находится в комнате, которая окружена стеной.
В комнате могут находится препятствия - тоже стены.
Робот не может пройти через стену.
Робот может перемещаться в 4х направлениях.
Каждая клетка комнаты может содержать мусор, который появляется в ней в неопределенный момент времени.
Каждый шаг робота стоит ему единицу энергии.
Чтоб очистить 10 единиц мусора роботу надо две еденицы энергии.
За один раз робот может очистить не больше 10 единиц мусора.

Задача в том, чтоб минимизировать затраты энергии и максимизировать кол-во убранного мусора.

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

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

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

Что надо:
Буду благодарна, если кто-то сможет предложить алгоритм, который будет более эффективен.


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

Спасибо

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

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

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

я тоже думаю, что в начале нужно узнать что из себя комната представляет.
иначе нечего оптимизировать. Дальше, есть известный алгоритм обхода площади (не помню точно как он называется).
Его смысл примерно в следующем. Разбиваем всю комнату на большие квадраты 2х2. дальше на новом графе местности ищем Minimum spanning tree. А дальше обходим это дерево по его контуру, получается такое циклическое движение, от куда начали, туда и вернулись, но при этом гарантированно обошли все клетки (маленькие) по одному разу в каждой (есть правдо еще по краям не затронутые клетки, которые образовались в случае, если не возможно полностью поделить площадь на большие квадраты: их надо отдельно обрабатывать).
Все это было бы оптимально, если бы не условие с энергией. Но здесь можно оптимизировать перебрав возможные spanning tree на предмет наибольшей близости точек окончания заряда, на пути обхода, к базе с зарядным устройством. Возможно МСТ можно даже с самого начала построить с такими требованиями, но это я уже не могу так на вскидку придумать.
Кстати, узнавать комнату можно постепенно. Скажем в начале можно сделать предположение, и начать обход. если во время обхода, реальность не совпадает с предположением, значит корректируем предположение и пересчитываем МСТ. Таким образом, в любое время, ведем себя может и не оптимально, но хотя бы рационально (т.е. думаем что оптимально).