Как научить робота проходить лабиринт?

Question

[Марат Ахметшин]

Как научить робота составлять карту лабиринта и ориентироваться на нее при прохождении? Из того, что имеется это датчик расстояния, датчик оборотов двигателя, датчик касания. Какую литературу прочитать для понимания и составления алгоритма?

Comments

[Василий]

www.astrolog.org/labyrnth/algrithm.htm а вот какие бывают лабиринты) в любом случае стоит хотя-бы краем глаза по диагонали посмотреть

Answer 1

[Сэр Кот]

Научить ходить вдоль одной стены, срабатывает в большинстве случаев

Comments

[Марат Ахметшин]

Задача в том, чтобы запомнить путь и пометить тупики как участки в которые нельзя возвращаться. Как это реализовать?

[Сэр Кот]

Представляете лабиринт как граф, где вершины - это перекрёстки, а рёбра - переходы между ними. Читаете про теорию графов в алгоритмах (как-то так) и пишите код

[Марат Ахметшин]

Здраво. Спасибо.

Answer 2

[riot26]

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

Comments

[Марат Ахметшин]

Хрошая идея! А как реализовать запоминания движения? Мне эта сфера незнакома.

[riot26]

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

[riot26]

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

Answer 3

[Vi]

Пусть сам учится.

Comments

[Марат Ахметшин]

Тролль?

[Vi]

Марат Ахметшин: нет, как по мне есть смысл больше думать о таком, в поисках алгоритма. Вон популярные иследования по прохождению крысы лабиринта без ошибки.

[Vi]

Марат Ахметшин: Ну что как там робот? получилось чтото ?

Answer 4

[VeyDlin]

Робот и правда может сам научится, хотя это не совсем подходит для лабиринтов.
Посмотрите пример: cs.stanford.edu/people/karpathy/convnetjs/demo/rld...