Гены Ардуинщика

z16sznwo1p4sg2a5jqlwy4qhxa0.jpeg

В очередной раз, при обдумывании самоделки на Atmega, встал вопрос проектирования соединений. В моем случае 12 внешних коннекторов и 21 связь. Расположение, соединение, пересечения, программирование, ошибки, ошибки, ошибки.

При кажущейся простоте задачи поломать мозг придется день, а то и два. Без опыта — месяц.
И… лень взяла свое.

Как это делается


Обычный алгоритм в таком случае:

  • используем макетную плату (самодельную или Arduino) не меняя или добавляя разъемы и разводку
  • подгоняем под макетку внешние коннекторы, чтобы не было пересечений
  • пишем программный код для настройки контроллера и макросы-переменные.


А что если последовательность пинов в коннекторах уже жестко заданы?

Как например у драйвера L298N. Пересечения проводов или дорожек сильно усложнят проектирование, сборку и эксплуатацию.

Попробуем решить задачу с помощью генетического алгоритма. И для начала определимся с моделью.

Список разъемов


  • Шина i2c для компаса I2C (SDA, SCL)
  • UART для связи с внешним миром UART (RXD, TXD)
  • Ультразвуковой сенсор SONAR1(Echo, Trig)
  • Управление маршевыми двигателями DRIVE (ENA, IN1, IN2, IN3, IN4, ENB) с помощью L298N — длинный коннектор как раз для шлейфа
  • Энкодер на колесе:
  • левый ENCODER_L (IN)
  • правый ENCODER_R (IN)
  • Сенсор-выключатель впереди робота:
  • левый SENS_L (IN)
  • правый SENS_R (IN)
  • Включение питания Мозга (OPI PC) CPU (EN)
  • Включение турбины VAC_CLEAN (EN)
  • Включение веника BROOM (EN)
  • Напряжение батареи и потребляемый ток PWR (LVL, CUR).


Модель


Получается ген длиной 21 хромосом, которые отображают пины микроконтроллера, а точнее их соединения с коннекторами.

VCC и GND пины коннекторов игнорируем, так как шины мы можем вынести за коннекторы.
Каждая ячейка может иметь значение от 1 до 32 (количество лап у микросхемы). Значения в гене не могут повторяться.

Не допускается пересечений проводников (соединения делаются последовательно, если следующий пин занят — проскакиваем далее)

Количество вариантов соединений:

$32^{21}=$ 40 564 819 207 303 340 847 894 502 572 032.

Правда это количество рассчитано для сочетаний с повторениями, но такой способ позволяет быстро оценить сложность.

Ускоряемся


Для уменьшения пространства поиска используем функции пина коннектора (ADC, INT, PWM, PCINT). Например, если пин может быть только ADC, то вести к нему линию PWM или дискретного входа бессмысленно.

Данный фильтр уменьшает количество вариантов до 8 748 869 014 201 881 088. Разница ощутима. Но миллиарды миллиардов вариантов это тоже много.

Так же ранее использовались «ручные» эмпирические правила:

  • начинаем процесс соединения с уникальных пинов (SDA, SCL, RXD, TXD)
  • после соединяем разъемы с большим количеством пинов
  • последними соединяем пины с более общим спектром функций.


Но волшебный Collections.shuffle задающий последовательность коннекторов для обработки, решает эту задачу успешно на автомате.

Решение


Запускаем алгоритм и получаем решение для Atmega328p TQFP32. У меня на бюджетном ноутбуке находит менее чем за минуту.

1 SONAR1.Echo
2 SONAR1.Trig
9 DRIVE.ENB
10 DRIVE.IN4
11 DRIVE.IN3
12 DRIVE.IN2
13 DRIVE.IN1
14 DRIVE.ENA
15 ENCODER_L.IN
16 VAC_CLEAN.EN
17 CPU.EN
22 PWR.LVL
23 PWR.CUR
24 SENS_R.IN
25 SENS_L.IN
26 ENCODER_R.IN
27 I2C.SDA
28 I2C.SCL
30 UART.RXD
31 UART.TXD
32 BROOM.EN

Алгоритм находит решение за пару тысяч эпох. Иногда не находит и за миллион. В таком случаем просто надо перезапустить программу, потому что инициализация происходит случайно.
Без фильтра по функциям пинов алгоритм так же находит решение. Правда за 74 минуты и 13 перезапусков алгоритма по миллиону эпох на каждый. Перед каждым запуском делаем shuffle последовательности соединений.

Остается только соединить проводами макетку или нарисовать дорожки на плате с микроконтроллером.

Детали


Чтобы описать всё, надо будет написать не одну статью. Я постарался комментировать непонятные и самые интересные моменты в java-коде.

Желающие углубиться в тему могут заглянуть в git-проекта.

© Habrahabr.ru