Component Centric Placement Using Deep Reinforcement Learning

Dit artikel presenteert een component-gerichte aanpak voor het automatiseren van de plaatsing van componenten op printplaten met behulp van Deep Reinforcement Learning, waarbij discretisatie en prior kennis de zoekruimte beperken en leiden tot mensachtige resultaten.

De kern

Stel je voor dat je een enorme, complexe puzzel moet leggen op een bord. Dit bord is een printplaat (PCB), het hart van elk elektronisch apparaat, van je smartphone tot je wasmachine. De puzzelstukjes zijn de elektronische onderdelen: grote chips (zoals de hersenen) en honderden kleine onderdelen (zoals de zenuwen en bloedvaten) die eromheen moeten worden geplaatst.

De uitdaging? Je moet deze stukjes zo neerzetten dat:

1. Ze niet op elkaar vallen (geen overlapping).
2. De draden die ze verbinden zo kort mogelijk zijn (voor snelheid en energie).
3. De kleine onderdelen dicht bij de grote chip zitten waar ze bij horen.

Vroeger deden mensen dit met de hand, of met simpele computerprogramma's die vaak vastliepen. In dit paper gebruiken de onderzoekers kunstmatige intelligentie (AI), specifiek een techniek genaamd Versterkend Leren (Reinforcement Learning), om dit probleem op te lossen.

Hier is hoe ze het aanpakken, vertaald naar alledaagse taal:

1. De "Centrale Hub" Strategie (Component Centric)

Stel je voor dat de grote chip in het midden van het bord een koning is. De kleine onderdelen zijn zijn hofhouding.

• Het oude probleem: De AI probeerde vaak willekeurige plekken op het hele bord te kiezen. Dit is als proberen een koning te vinden in een heel land zonder kaart. Te veel opties, te veel chaos.
• De nieuwe oplossing: De onderzoekers zeggen: "Laten we de koning vast in het midden zetten." De AI hoeft nu alleen nog maar te beslissen waar de hofhouding (de kleine onderdelen) rondom de koning gaat staan.
• Het effect: In plaats van een heel land te doorzoeken, zoekt de AI alleen in de straten rondom het paleis. Dit maakt de puzzel veel kleiner en sneller op te lossen.

2. De "Netwerk-Geheugen" (Net Proximity)

Elk klein onderdeel heeft een specifieke taak en moet verbonden zijn met een specifieke "voedingsbron" op de grote chip.

• De analogie: Stel je voor dat je een feestje geeft. Je weet dat de gasten die van kaas houden, dicht bij de kaasplank moeten zitten, en de wijnliefhebbers bij de wijnkast.
• De slimme truc: De AI krijgt een hint (een beloning) als hij een onderdeel neerzet dicht bij de juiste "wijnkast" (de pin op de chip). Als hij het verkeerd doet, krijgt hij geen punten. Hierdoor leert de AI niet door blind te gissen, maar door slimme hints te gebruiken die al in het ontwerp zitten.

3. De AI Spelers (De Methoden)

De onderzoekers testten drie verschillende "spelers" om te zien wie de beste puzzellegger is:

• Simulated Annealing (SA): Dit is als een geduldige, oude meester. Hij probeert een oplossing, kijkt of het beter is, en als het iets slechter is, probeert hij het soms toch om uit een "doodlopende straat" te komen. Hij is goed, maar soms traag.
• DQN (Deep Q-Network): Dit is een snelle, instinctieve speler. Hij leert door te kijken naar wat er direct gebeurt. "Als ik hier neerzet, krijg ik punten." Hij is snel, maar mist soms het grotere plaatje.
• A2C (Actor-Critic): Dit is een tandem-paar. De "Actor" probeert een zet te doen, en de "Critic" (de trainer) zegt direct: "Goed gedaan" of "Nee, dat was dom." Ze werken samen om de beste strategie te vinden.

4. Het Geheime Wapen: "Token" Invoer

In het begin keek de AI alleen naar de onderdelen zelf (bijv. "dit is een weerstand"). Maar de onderzoekers merkten dat dit niet genoeg was.

• De verbetering: Ze gaven de AI ook de naam van de groep waar het onderdeel bij hoort (bijv. "deze weerstand hoort bij de voedingsspanning").
• Het resultaat: De AI begon te begrijpen: "Ah, deze twee onderdelen horen bij dezelfde groep, dus ze moeten dicht bij elkaar zitten." Dit was als het geven van een extra kaart in een kaartspel. De resultaten verbeterden enorm.

Wat was het resultaat?

Toen ze dit systeem testten op echte, complexe printplaten:

• De AI kon net zo goed (en soms zelfs beter) zijn als een menselijke expert.
• De draden werden korter (wat betekent snellere apparaten en minder energie).
• Er waren minder fouten, zoals onderdelen die op elkaar lagen (wat in de echte wereld onmogelijk is).

Kortom:
De onderzoekers hebben een slimme manier bedacht om AI te leren printplaten te ontwerpen. Door de puzzel te vereenvoudigen (alles rondom één centrum) en de AI slimme hints te geven over welke onderdelen bij elkaar horen, kunnen computers nu complexe elektronische ontwerpen maken die bijna net zo goed zijn als die van de beste menselijke ingenieurs. Het is alsof je een AI hebt die niet alleen ziet waar de stukjes passen, maar ook begrijpt waarom ze daar moeten zitten.

Technische samenvatting

Titel: Component-gecentreerde plaatsing met behulp van Deep Reinforcement Learning

1. Het Probleem

De geautomatiseerde plaatsing van componenten op printplaten (PCB's) is een kritieke stap in het ontwerp, maar vormt een unieke uitdaging vergeleken met plaatsing op chips (SoC) of chiplets. De specifieke moeilijkheden voor PCB's zijn:

• Variatie in componentgrootte: Componenten variëren sterk in afmetingen.
• Complexiteit van de board: Ondersteuning voor zowel enkel- als dubbelzijdige boards.
• Beperkingen: Strikte eisen aan draadlengte (wirelength), congestie en de noodzaak om overlappingen te voorkomen voor fabricage.
• Zoekruimte: Traditionele methoden (analytisch, partitionering, gesimuleerde afkoeling) en zelfs recente Reinforcement Learning (RL) methoden worstelen met de enorme zoekruimte en de noodzaak om zowel discrete als continue constraints te hanteren.

2. Methodologie

De auteur stelt een nieuwe aanpak voor die Reinforcement Learning (RL) combineert met een component-gecentreerde lay-outstrategie.

A. Component-gecentreerde Lay-out
In plaats van de PCB als een continu 2D-vlak te modelleren (wat leidt tot irrelevante kleine verschuivingen en een explosie van de zoekruimte), wordt de PCB gemodelleerd als een centraal hoofdcomponent (bijv. microcontroller) omringd door een set vaste, discrete kandidaat-locaties.

• Discrete Actieruimte: De actie-ruimte bestaat uit een set van $N$ discrete fysieke locaties. Dit verkleint de zoekruimte drastisch terwijl alle haalbare plaatsingen behouden blijven.
• Net-proximiteit: Er wordt gebruikgemaakt van voorkennis uit het schema: passieve componenten moeten dicht bij hun bijbehorende spanningsbron (power pins) worden geplaatst. Dit leidt tot kortere bedrading en minder overlapping.

B. RL Architectuur en Beloningsfunctie
Het probleem wordt geformuleerd als een Markov Decision Process (MDP):

• State ($S$): Een one-hot vector die het huidige te plaatsen component (passief) en het bijbehorende net-ID aangeeft. Dit "token-based" input helpt de RL-agent om langetermijnrelaties te begrijpen (componenten op hetzelfde net moeten dicht bij elkaar).
• Actie ($A$): Het kiezen van een van de $N$ discrete locaties voor het huidige component.
• Beloningsfunctie ($R_{total}$): Een gewogen som van twee componenten:
  1. Overlap-voorkoming ($R_{non-overlap}$): Geeft een beloning als er geen fysieke overlapping is met andere geplaatste componenten.
  2. Net-proximiteit ($R_{proximity}$): Geeft een beloning als het component dicht bij de bijbehorende power pin wordt geplaatst.
  • Formule: $R_{total} = \alpha R_{non-overlap} + (1-\alpha) R_{proximity}$
  • Om de exploratie te verbeteren, wordt een "Top-K" strategie gebruikt die de beloning uitbreidt naar de $K$ dichtstbijzijnde buren van de ideale locatie, zodat de agent niet vastloopt in lokale optima.

C. Gebruikte Algoritmen
De studie vergelijkt verschillende RL-methoden en een klassieke benchmark:

• Deep Q-Network (DQN): Geschikt voor discrete actieruimtes.
• Advantage Actor-Critic (A2C): Combineert waarde- en policy-based learning.
• Simulated Annealing (SA): Een traditionele optimalisatiemethode.
• DQNnet: Een variant van DQN die expliciet net-ID informatie in de state-opname integreert.

D. Metriek: Totale Euclidische Draadlengte (TEWL)
In plaats van de gebruikelijke Half Perimeter Wirelength (HPWL), gebruikt dit werk TEWL. TEWL berekent de werkelijke afstand tussen alle pinnen van een net, wat een betere correlatie biedt met de daadwerkelijke bedrading dan HPWL (die alleen de omhullende doos bekijkt).

3. Belangrijkste Bijdragen

1. Component-gecentreerde Discretisatie: Een innovatieve manier om de PCB-plaatsing te reduceren tot een discrete zoekruimte rond een hoofdcomponent, wat de complexiteit van RL aanzienlijk verlaagt.
2. Integratie van Net-kennis: Het introduceren van net-ID's in de state-representatie (token-based input) en het gebruik van net-proximiteit in de beloningsfunctie, wat de exploratie van onhaalbare ruimtes voorkomt.
3. Vergelijkende Analyse: Een uitgebreide evaluatie van DQN, A2C en SA op real-world datasets, waarbij wordt aangetoond dat het combineren van net-informatie met DQN (DQNnet) superieure resultaten oplevert.

4. Resultaten

De methode is getest op 9 real-world PCB's met variërende complexiteit (van 8 tot 24 passieve componenten).

• Prestaties (TEWL):
  • De meeste ML-methoden (DQN, A2C) presteren beter dan menselijke ontwerpen (Ground Truth) op het gebied van TEWL, behalve bij de meest complexe cases (U20, U26).
  • A2C presteert over het algemeen het beste op TEWL, maar is minder robuust bij zeer complexe boards en heeft meer routing-conflicten.
  • DQNnet (DQN met net-informatie) toont de grootste verbetering ten opzichte van standaard DQN. Het reduceert de TEWL aanzienlijk en vermindert het aantal overlappingen drastisch vergeleken met standaard DQN.
• Visuele Inspectie:
  • Hoewel A2C de beste TEWL-scores heeft, vertoont het meer overlappingen en routing-conflicten in complexe scenario's.
  • DQNnet biedt een uitstekende balans: het behoudt lage TEWL-waarden en minimaliseert overlappingen effectiever dan de andere methoden.
• Vergelijking met Menselijk Ontwerp: De beste voorgestelde methode (DQNnet) benadert menselijke plaatsingen qua kwaliteit en haalbaarheid, en overtreft deze vaak op het gebied van draadlengte.

5. Significantie

Dit werk is significant omdat het een brug slaat tussen traditionele PCB-ontwerppraktijken en moderne AI-technieken.

• Het lost het probleem van de "grote zoekruimte" op door een domeinspecifieke discretisatie toe te passen.
• Het bewijst dat het integreren van domeinkennis (zoals net-proximiteit) in de RL-beloningsfunctie en state-representatie essentieel is voor succesvolle toepassing op complexe engineeringproblemen.
• De resultaten suggereren dat AI-gestuurde plaatsing niet alleen haalbaar is, maar ook superieur kan zijn aan menselijke ontwerpen in termen van efficiëntie (draadlengte), terwijl het tegelijkertijd de fabricage-eisen (geen overlapping) respecteert.

Kortom, de paper presenteert een robuust framework voor geautomatiseerde PCB-plaatsing dat RL-methoden effectief toepasbaar maakt door de zoekruimte slim te beperken en de beloningsstructuur te aligneren met fysieke ontwerpprincipes.