В очередной раз, при обдумывании самоделки на 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-проекта.
Автор: Максим Завало
