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

В очередной раз, при обдумывании самоделки на 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 (количество лап у микросхемы). Значения в гене не могут повторяться.

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

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

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-проекта.