Самый быстрый алгоритм для определения местоположения объекта в поле
Каков был бы лучший алгоритм с точки зрения скорости для обнаружения объекта в поле?
Поле состоит из 18 на 18 квадратов с длиной стороны 30,48 см. Робот находится в квадрате (0,0), и его задача - добраться до источника света, избегая при этом препятствий на пути. Чтобы найти источник света, робот делает поворот на 360 градусов, чтобы найти угол с наибольшим показанием света, а затем движется к источнику. Он может надежно обнаружить источник света от 100 см.
В настоящее время я реализую это, сохраняя информацию о каждой плитке в массиве 2x2. Возможные значения плиток: неисследованные (по умолчанию), заблокированные (есть препятствие), пустые (там ничего нет). Я думаю об использовании алгоритма DFS, когда дети находятся в положении (i+3,j) или (i,j+3). Однако, учитывая тот факт, что я буду делать поворот, чтобы определить угол с наибольшим показателем освещенности у каждого ребенка, я думаю, что может существовать алгоритм, который может определить источник света быстрее, чем DFS. Кроме того, я буду путешествовать только в направлениях x и y, так как робот будет использовать линии сетки на полу, чтобы внести поправки в свои положения x и y.
Я был бы признателен, если бы для решения этой задачи был предложен быстрый и надежный алгоритм.
2 ответа
Это действительно широкий вопрос, и я не эксперт, поэтому мой ответ основан на мышлении "первых принципов", а не на практическом опыте.
(Я предполагаю, что ваш робот обычно имеет беспрепятственную линию обзора и движения; т.е. это открытая область с рассеянными препятствиями, а не в лабиринте.)
Проблема заключается в интерпретации информации, которую вы получаете после сканирования на 360 градусов.
Если робот видит источник света, то обход маршрута к источнику света является либо тривиальным, либо "простым" заданием по ходьбе по лабиринту.
Сложность в том, когда вы не видите источник. Это может означать, что источник находится вне круга видимости. Но это также может означать, что свет находится за препятствием. И, к сожалению, простой датчик, который вы описываете, не может различить эти два случая.
Если ваша сенсорная система позволяла вам видеть препятствия, вы могли бы наносить на карту местоположения "теневых" областей (областей позади препятствий), и использовать это, чтобы отследить места, которые оставлены для поиска. Таким образом, ваша стратегия состоит в том, чтобы посетить небольшое количество мест и выполнить сканирование каждого, а затем методично "убрать" небольшое количество областей, которые были в тени.
Но поскольку вы не можете легко определить, где находятся теневые области, вам нужен алгоритм, который (в конечном счете) ищет везде. DFS - это общая стратегия, которая ищет везде, но делает это (по сути), сначала заглядывая в закоулки. Лучшей стратегией является поиск в ширину и посещение уголков и закоулок только в том случае, если в ходе масштабных сканирований источник света не обнаружен.
Я был бы признателен, если бы для решения этой задачи был предложен быстрый и надежный алгоритм.
Я думаю, что вам нужно будет разработать его самостоятельно. (Разве это не проблема / задача / соревнование?)
Хотя это может выглядеть не так, это больше похоже на проблему следования лабиринта, чем на что-либо еще. Я полагаю, что это какая-то сложная ситуация или соревнование, где всегда есть путь от начала до цели, но предположим, что нет ни минуты. Одним из успешных результатов для робота, управляющего маяком, полностью окруженным препятствиями, будет отчет с описанием замкнутого пути препятствий, окружающих сигнал. Если нет такого замкнутого пути, то где-то можно найти дыру; Вот почему выглядит как лабиринт.
Таким образом, основной алгоритм, который я выбрал бы, - это начать с проходящего по спирали внутрь, выметая путь, достаточно узкий, чтобы вы наверняка увидели маяк, если он есть. Если нет никаких препятствий (вырожденный случай), это находит цель за минимальное время. (Подсказка: каждый ход уменьшает количество ячеек, которые ваш датчик может найти за шаг.)
Возьмите спиральный обход против часовой стрелки. То, что у вас есть, связано с правилом решения лабиринтов, удерживая правую руку на стене и следуя сгенерированному пути. В этом случае у вас есть осложнение, что, хотя начало лабиринта находится на границе, конца может и не быть. В такой ситуации возможен сбой с пути, касающегося правой руки. Обнаружение этой ситуации требует поиска "полостей" в области, сметенной соседством со стеной.