Цифровая карта в алгоритме поиска A* в Arduino

В качестве дипломного проекта я создаю автоматизированное управляемое транспортное средство. Я новичок в алгоритмах поиска пути и на данный момент работал только с небольшими проектами на базе Arduino. Я выбрал поиск A* после тщательного понимания многих других алгоритмов (Дийкстры/D* и т. д.) и использования Arduino Uno (позже перейду на Due) для робота.

Я также реализовал код A* на C++.

Но я застрял в его реализации в Arduino. Я не знаю, как создать цифровую карту арены (я использую площадь 4 кв. м и сетку 10х10). Я понятия не имею, как перемещать робота по этой арене с помощью цифровой карты (думаю, для ориентации мне потребуются колесные энкодеры и ультразвуковой датчик, установленный на сервоприводе).

Моя главная проблема — создать цифровую карту арены и как это сделать.

Я прилагаю для справки код A* и используемую в нем сетку.

// Программа-драйвер для проверки вышеуказанной функции
int main() 
{ 
  //* Описание сетки-
   1--> The cell is not blocked 
   0--> The cell is blocked    *//
  int grid[ROW][COL] = 
  { 
    { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 }, 
    { 1, 1, 1, 0, 1, 1, 1, 0, 1, 1 }, 
    { 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 }, 
    { 0, 0, 1, 0, 1, 0, 0, 0, 0, 1 }, 
    { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 }, 
    { 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 }, 
    { 1, 0, 0, 0, 0, 1, 0, 0, 0, 1 }, 
    { 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 }, 
    { 1, 1, 1, 0, 0, 0, 1, 0, 0, 1 } 
  }; 

  // Источник — самый левый и нижний угол
  Pair src = make_pair(8, 0); 

  // Пункт назначения — самый левый верхний угол
  Pair dest = make_pair(0, 0); 

  aStarSearch(grid, src, dest); 

  return(0); 
}

, 👍0

Обсуждение

Это вопрос о том, как создать компактное графическое представление?, @Mikael Patel

Сетка может быть представлена двумерным массивом., @chrisl

@chrisl У меня есть 2D-массив, реализованный в моей программе на C++, но я не знаю, как преобразовать его в реальный мир., @user177195

Я не очень понимаю, в чем ваша проблема. У вас есть поле, по которому должен двигаться робот. Это поле состоит из свободного пространства и препятствий. Для каждого препятствия вы помещаете ноль в соответствующий элемент массива и 1 в противном случае. Вот и весь процесс кодирования вашего лабиринта «реального мира». Конечно, размером сетки 10х10 полей вы ограничили разрешение. Вы не можете представлять структуры меньшего размера без использования более высокого разрешения., @chrisl

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

У вас есть код для перемещения двигателей робота? Вы можете написать по одной функции для перемещения в каждом направлении. Это во многом зависит от вашего робота. Затем вам следует определить переменные положения для x и y, которые соответствуют индексам элементов в двумерном массиве сетки. Вы не предоставили реализацию своего алгоритма StarSearch, поэтому мы не знаем, как он представляет найденный путь по лабиринту. Вам придется последовательно менять переменные позиции в соответствии со следующей позицией в сетке и соответственно перемещаться., @chrisl


1 ответ


1

Во-первых, вам нужен 2D-массив для хранения сегментов карты. тогда вам придется обновить их в соответствии с реальной картой. вам необходимо принять несколько мер:

  1. ряд датчиков для оценки соседних сегментов. например, стены/дорога. Края карты считаются стенами.
  2. массив (список) текущих соседних сегментов. (просто массив из 4 элементов, содержащий положение вверх/вниз/влево/вправо. Этот массив хранит индекс упомянутых сегментов в основном 2D-массиве.)
  3. маяк или что-то в этом роде на позиции ворот. вы можете оценить сегменты на основе расстояния от маяка. (самый простой метод, декартово расстояние).
  4. запустите итерацию алгоритма A*, чтобы определить, какой соседний сегмент подходит для следующего хода.
,

Спасибо за помощь, но я до сих пор не понимаю, как преобразовать 2D-массив в реальную карту мира. В качестве справки я прилагаю пример алгоритма A* и используемого в нем массива. Можете ли вы, пожалуйста, рассказать немного больше?, @user177195

если я правильно понял ваш вопрос, это точно так же, как сетка, которую вы поместили в свой код. карта сегментируется в мозгу робота по сетке. поэтому элемент массива (например,grid[3][3]) показывает местоположение на вашей карте (например, примерно на северо-востоке карты). ваш робот должен двигаться сегментами, которые считаются «незаблокированными» и связаны друг с другом. @user177195, @Tirdad Sadri Nejad

Да, это правильно. Я просто не знаю, как связать это место на моей карте с координатами в сетке. Если для этого есть какой-то устоявшийся алгоритм, то, пожалуйста, дайте мне знать., @user177195