💻 computer science

Separation Logic for Verifying Physical Collisions of CNC Programs

Dit artikel presenteert een formeel verificatiekader dat de CNC-werkruimte modelleert als een ruimtelijke heap en Separation Logic toepast om fysieke botsingen te detecteren als logische data-races, waardoor de afhankelijkheid van iteratieve simulatie voor veiligere, autonome productie wordt verminderd.

Oorspronkelijke auteurs: Yeonseok Lee

Gepubliceerd 2026-05-21

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yeonseok Lee

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een hoogwaardige, geautomatiseerde fabriek runt waar een robotarm (de CNC-machine) een stuk metaal bewerkt. Traditioneel voeren ingenieurs duizenden computersimulaties uit om ervoor te zorgen dat de robot niet zijn eigen arm in het metaal of de tafel slaat. Ze kijken hoe de robot zich beweegt in een virtuele wereld, in de hoop een botsing te detecteren voordat deze in het echt plaatsvindt. Maar als je het ontwerp zelfs maar een klein beetje aanpast, moet je al die simulaties opnieuw uitvoeren. Het is traag, repetitief en biedt geen 100% garantie.

Dit artikel stelt een volledig andere manier van denken over veiligheid voor. In plaats van naar een film van de bewegende robot te kijken, behandelt het de fabrieksvloer als het geheugen van een computer.

Hier is de eenvoudige uiteenzetting van hun idee:

1. De fabrieksvloer is een "geheugennet"

Stel je voor dat de volledige werkruimte van de machine een gigantisch 3D-rooster is van kleine kubussen (zoals pixels, maar in 3D).

De oude manier: Je berekent de exacte kromme van de robotarm terwijl deze door de lucht beweegt. Dit wiskundig rommelig en moeilijk te bewijzen dat het veilig is.
De nieuwe manier: De auteurs zeggen: "Laten we stoppen met ons zorgen te maken over de gladde krommen. Laten we gewoon kijken welke kubussen bezet zijn."
- Als een kubus de Houder bevat, is deze gemarkeerd als "Houder".
- Als een kubus de Metaalblok bevat, is deze gemarkeerd als "Grondstof".
- Als een kubus een Klem bevat, is deze gemarkeerd als "Omgeving".
- Als een kubus leeg is, is deze gemarkeerd als "Leeg".

2. De "Parser-Prover Handdruk" (De Vertaler)

De machine spreekt een taal van gladde, drijvende-kommagetallen (zoals X = 10,5432). De veiligheidscontroleur spreekt een taal van strikte, gehele getallen (zoals "Kubus 10", "Kubus 11").

Het artikel introduceert een Vertaler (de Parser) die tussen de machinencode en de veiligheidscontroleur zit.

De Taak: De Vertaler neemt het gladde, wiebelige pad dat de robot zou kunnen nemen en koppelt dit vast aan de dichtstbijzijnde roosterkubussen. Het voegt ook een kleine "veiligheidsbuffer" toe (zoals het dragen van een vachtige jas om de houder) om ervoor te zorgen dat, zelfs als de robot een klein beetje wiebelt, het niets raakt.
Het Resultaat: Tegen de tijd dat de veiligheidscontroleur het probleem ziet, zijn er geen wiebelige lijnen of decimalen meer. Het is gewoon een lijst met specifieke kubussen: "De houder is hier, het metaal is daar, en het pad is vrij."

3. Botsingen zijn "Data-races"

In computerprogrammering treedt een "data-race" op wanneer twee programma's tegelijkertijd proberen naar dezelfde geheugenplek te schrijven, wat een crash veroorzaakt.

Het Grote Idee van het Artikel: Een fysieke crash in een fabriek is precies hetzelfde. Als de "Houder" probeert eigendom te claimen van een kubus die al eigendom is van de "Klem", is dat een Ruimtelijke Data-race.
De Logica: De auteurs gebruiken een speciaal wiskundig systeem genaamd Scheidingslogica. Dit systeem heeft een simpele regel: Twee dingen kunnen niet tegelijkertijd hetzelfde stuk ruimte bezitten.
De Check: De veiligheidscontroleur (de Prover) kijkt naar de lijst met kubussen. Het vraagt: "Overlap de lijst met kubussen van de Houder met de lijst van de Klem?"
- Als het antwoord Nee is, is de beweging veilig.
- Als het antwoord Ja is, zegt de wiskunde direct "ONWAAR". Het systeem stopt de machine direct, bewijzend dat een crash zou gebeuren, zonder ooit een trage simulatie te hoeven uitvoeren.

4. Metaal snijden is "Geheugen verwijderen"

Wanneer de robot het metaal snijdt, verwijdert het materiaal.

In dit nieuwe systeem is snijden niet alleen een visuele verandering; het is een logische update.
Terwijl de houder door de metaalkubussen beweegt, verandert het systeem die kubussen logisch van "Grondstof" naar "Leeg".
Het is alsof je Tetris speelt, waarbij de vakjes die het blok raakt verdwijnen van het bord terwijl het blok valt. De wiskunde bewijst dat de houder alleen vakjes raakt die daadwerkelijk "Grondstof" waren en geen "Klem".

5. Samenwerken (Concurrentie)

Wat als je twee robots hebt die aan dezelfde tafel werken?

Het artikel gebruikt een uitbreiding van hun logica om dit te hanteren. Het behandelt de werkruimte als een gedeeld kantoor.
Als Robot A een specifiek gebied (een "overdrachtszone") moet gebruiken om een onderdeel aan Robot B door te geven, fungeert het systeem als een vergrendeling.
Robot A "vergrendelt" de zone (claimt eigendom van die kubussen). Robot A kan die zone niet betreden totdat Robot A klaar is en de zone "ontgrendelt" (de kubussen teruggeeft aan "Leeg").
Dit voorkomt dat de twee robots in elkaar botsen, omdat de wiskunde bewijst dat ze nooit tegelijkertijd dezelfde "vergrendeling" kunnen vasthouden.

6. Draaiende tafels (5-assige machines)

Sommige machines hebben tafels die draaien terwijl de houder beweegt. Dit is meestal zeer moeilijk te berekenen.

De truc van het artikel: De Vertaler (Parser) doet al het zware draaiende rekenwerk voordat de veiligheidscontroleur ernaar kijkt.
Het berekent precies welke kubussen het draaiende metaalblok zal doorlopen en zet dit om in een simpele lijst van "Bezette Kubussen".
De veiligheidscontroleur controleert vervolgens alleen of de lijst van de Houder en de lijst van het Draaiende Metaal overlappen. Als ze dat niet doen, is de beweging veilig.

Samenvatting

In plaats van te proberen de fysica van een crashende robot te simuleren, verandert dit artikel de fabrieksvloer in een logisch raadsel.

Vertaal het gladde pad van de robot naar een rooster van kubussen.
Controleer of de kubussen van de Houder overlappen met de kubussen van de Klem of het Metaal.
Bewijs de veiligheid door te laten zien dat ze volledig gescheiden zijn (disjunct).

Als de wiskunde zegt dat de kubussen niet overlappen, is de machine gegarandeerd veilig. Als ze wel overlappen, bewijst de wiskunde dat een crash onvermijdelijk is, waardoor de machine stopt voordat deze zelfs maar begint. Dit vervangt duizenden trage, repetitieve tests door een enkele, directe wiskundige bewijslast.

Technische Samenvatting: Splitsingslogica voor het Verifiëren van Fysieke Collisies van CNC-Programma's

1. Probleemstelling

Traditionele veiligheidsverificatie voor Computer Numerical Control (CNC)-bewerkingen is sterk afhankelijk van geometrische simulaties en analyse van doorgestreepte volumes. Hoewel deze methoden effectief zijn voor het identificeren van voor de hand liggende G-code-fouten, kampen ze met fundamentele beperkingen:

Gebrek aan Symbolisch Bewijs: Ze bieden probabilistisch vertrouwen in plaats van deterministische, symbolische bewijzen van veiligheid.
Berekeningskosten: Ze vereisen repetitieve testcycli, vooral wanneer specificaties of G-code veranderen.
Omgaan met Onzekerheid: Ze worstelen om continu kinematische variabelen, niet-deterministische snelle positioneringspaden en mechanische variabiliteiten (bijv. servo-lag) strikt te kwantificeren zonder rekenkundig duur te worden.
Schaalbaarheid: Bestaande methoden schalen vaak niet efficiënt naar complexe multi-as-omgevingen (bijv. 5-as Tafel-Tafel-configuraties) en collaboratieve multi-gereedschapssystemen.

Het artikel stelt dat fysieke collisies in CNC-bewerkingen kunnen worden herdefinieerd als logische contradicties binnen een beheerd bronnenmodel, wat een deterministisch alternatief biedt voor stochastische simulatie.

2. Methodologie

Het voorgestelde kader introduceert een Parser-Prover Handshake-architectuur die continue fysieke kinematica ontkoppelt van discrete formele logica. Deze benadering conceptualiseert de fysieke CNC-werkruimte als een Spatiale Heap, waarbij fysieke bezetting wordt behandeld als een beheerde logische bron.

2.1 Architecturale Ontkoppeling

Het systeem werkt via een strikte grens tussen twee domeinen:

De Parser (Continue Domein): Treedt op als een virtuele machine die ruwe G-code, gereedschapsgeometrie en veiligheidsmarges verwerkt. Het reduceert continue kinematische variabelen (drijvende-kommacoördinaten, voedingssnelheden) en fysieke onzekerheden naar een discreet geheelgetal-domein ( $Z^3$ ). Het maakt gebruik van Minkowski-sommen om gereedschapsvolumes uit te breiden met een door de gebruiker gedefinieerde veiligheidsmarge ( $\epsilon$ ) en hanteert Bresenhams 3D-algoritme om discrete voxel-paden te genereren voor lineaire interpolatie (G01) en omhullende dozen voor snelle positionering (G00).
De SL-Prover (Discreet Domein): Werkt strikt op de discrete ruimtelijke verzamelingen die door de Parser worden uitgezonden. Het fungeert als een geheugenbeheerder en evalueert Splitsingslogica (SL)-triplets tegen een Spatiale Heap ( $h$ ). De Prover vraagt geen variabele opslag op; het valideert uitsluitend ruimtelijke disjunctie.

2.2 Het Spatiale Heap-model

De fysieke werkruimte wordt in kaart gebracht naar een eindige partiële functie $h: Z^3 \rightharpoonup \{Gereedschap, Omgeving, Grondstof, Leeg\}$ .

Ruimtelijke Data-races: Fysieke collisies worden herdefinieerd als "Ruimtelijke Data-races", die optreden wanneer twee verschillende fysieke bronnen (bijv. Gereedschap en Omgeving) tegelijkertijd proberen eigendom te claimen van hetzelfde discrete geheugenadres.
Scheidende Conjunctie ( $*$ ): De kernlogische operator stelt dat subformules gelden voor disjuncte delen van het geheugen. Als $R(C_1, \theta_1) * R(C_2, \theta_2)$ wordt geëvalueerd, is dit alleen vervulbaar als $C_1 \cap C_2 = \emptyset$ . Een niet-lege doorsnede maakt de logica onvoldoende, wat deterministisch een fout signaleert.

2.3 Verificatiepijplijn

Het verificatieproces volgt een unidirectionele pijplijn:

Input: Ruwe G-code, gereedschapsmaskergeometrie, veiligheidsmarge ( $\epsilon$ ) en resolutiefactor.
Discretisatie: De Parser converteert input naar discrete ruimtelijke verzamelingen ( $V_{start}, V_{final}, V_{path}$ ).
Logische Inferentie: De Prover evalueert de Splitsingslogica Triple $\{ \Sigma_0 \} \text{CSL} \{ \Sigma_{final} \}$ ${Σ_{0}} CSL {Σ_{f ina l}}$ .
- Preconditie ( $\Sigma_0$ ): Stelt de initiële disjuncte eigendom vast van het gereedschap, de omgeving, de grondstof en de lege ruimte.
- Opdracht (CSL): Vertegenwoordigt de discrete beweging (bijv. G00, G01) als heap-mutaties.
- Postconditie ( $\Sigma_{final}$ ): Stelt de bijgewerkte eigendom vast na de verplaatsing van het gereedschap en materiaalverwijdering.

2.4 Uitbreidingen naar Concurrentie en Multi-as

Concurrente Splitsingslogica (CSL): Voor multi-gereedschap of collaboratieve omgevingen wordt de Spatiale Heap gepartitioneerd in thread-lokale sub-heaps ( $h_{local}$ ) en een gedeelde heap ( $h_{shared}$ ). Fysieke overdrachten worden geverifieerd als formele eigendomsoverdrachten met behulp van Kritieke Regio's (with Res do C), wat wederzijdse uitsluiting garandeert zonder dynamische vergrendelingen.
Multi-as Kinematica: Het kader schaalt naar 5-as-operaties door het snijgereedschap en het roteerbare werkstuk te behandelen als twee concurrerende, wederzijds mutabele ruimtelijke threads. De Parser berekent vooraf het roterende doorgestreepte volume van de grondstof (met rotatiematrices) en het lineaire doorgestreepte volume van het gereedschap, en presenteert beide als discrete verzamelingen aan de Prover. Dit abstraheert complexe trigonometrische kinematica weg van het bewijsengine.

3. Belangrijkste Bijdragen

Formele Herdefinitie van Collisies: Het artikel vestigt een formele correspondentie tussen fysieke bezetting en logische geheugeneigendom, en herdefinieert fysieke collisies als logische "Ruimtelijke Data-races".
Parser-Prover Handshake: Een nieuwe architecturale grens die continue onzekerheden reduceert naar een discreet geheelgetal-domein, waardoor de Prover kan opereren binnen een hanteerbaar fragment van Splitsingslogica, terwijl de complexiteit van algemene pointerarithmetic wordt vermeden.
Integratie van Geometrische Veiligheidsmarges: De methodologie integreert Minkowski-sommen om formele veiligheidsmarges ( $\epsilon$ ) direct binnen de discrete logica te bieden, rekening houdend met real-world mechanische onzekerheden.
Schaalbaarheid naar Geavanceerde Kinematica: Het kader ondersteunt native multi-as (bijv. 5-as) en gelijktijdige multi-gereedschap-omgevingen door het werkstuk te modelleren als een dynamisch mutabele ruimtelijke bron en Concurrente Splitsingslogica te gebruiken voor verificatie van gedeelde werkruimtes.

4. Resultaten en Validatie

Het artikel demonstreert de methodologie door middel van:

Deterministische Verificatie: Het systeem verifieert succesvol veilige trajecten door de vervulbaarheid van Splitsingslogica-triplets te bewijzen.
Collisiedetectie: In een case study waarbij een snelle doortocht in een klemvoorziening plaatsvond, detecteert het systeem een "Ruimtelijke Data-race" (niet-lege doorsnede van geclaimd geheugen) en schakelt deterministisch over naar een fouttoestand, voordat fysieke uitvoering plaatsvindt.
Concurrentie en Overdrachten: Het kader valideert parallelle uitvoering van dubbele gereedschappen in disjuncte ruimtes en de veilige sequentiële overdracht van een gedeelde bron, bewijzend dat de scheidende conjunctie wederzijdse uitsluiting afdwingt.
Multi-as Verificatie: De benadering verifieert succesvol 5-as-operaties door complexe roterende kinematica te reduceren tot discrete voxel-verzamelingen, bewijzend dat de paden van het gereedschap en de grondstof de omgeving of elkaar niet snijden.

5. Betekenis en Claims

Het artikel claimt dat deze benadering een deterministisch alternatief biedt voor traditionele geometrische simulatie, waarbij symbolische bewijzen van veiligheid worden geboden in plaats van probabilistisch vertrouwen. Door te fungeren als een aanvulling op simulatie, streeft het kader ernaar om:

Iteratief Testen te Verminderen: Het aantal vereiste testcycli te minimaliseren wanneer G-code of specificaties veranderen.
Autonome Productie mogelijk te Maken: Een wiskundig onderbouwde basis te bieden voor autonome, minder-collisieve productiesystemen.
Complexiteit te Ontkoppelen: De rekenkundige last van continue kinematica te scheiden van het logische bewijs, waardoor formele verificatie hanteerbaar wordt voor complexe industriële toepassingen.

De auteurs positioneren dit werk niet als een vervanging voor alle simulatie, maar als een rigoureuze, schaalbare laag die ervoor zorgt dat veiligheidsvoorwaarden worden voldaan voordat staatsovergangen plaatsvinden, wat mechanische semantiek nabootst die in andere domeinen zoals additieve productie wordt gebruikt. Toekomstig werk wordt opgemerkt om "Incorrectness Splitsingslogica" te verkennen voor het isoleren van legacy-bugs en real-time integratie in ingebouwde controllers.