💻 computer science

Multi-Objective Statistical Model Checking using Lightweight Strategy Sampling (extended version)

Dit artikel presenteert de eerste statistical model checking-benadering voor multi-objective Pareto-queries met behulp van lightweight strategy sampling, met een incrementeel schema voor asymptotische convergentie en heuristische methoden voor eindtijdbenaderingen, die zijn geïmplementeerd en gevalideerd binnen de Modest Toolset.

Oorspronkelijke auteurs: Pedro R. D'Argenio, Arnd Hartmanns, Patrick Wienhöft, Mark van Wijk

Gepubliceerd 2026-07-02

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Pedro R. D'Argenio, Arnd Hartmanns, Patrick Wienhöft, Mark van Wijk

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 de kapitein bent van een ruimteschip. Je hebt twee hoofddoelen: je wilt zoveel mogelijk schatten verzamelen (beloning maximaliseren), maar je wilt ook zo min mogelijk brandstof gebruiken (kosten minimaliseren).

Het probleem is dat deze twee doelen met elkaar in strijd zijn. Als je snel gaat om meer schatten te bemachtigen, verbruik je meer brandstof. Als je langzaam gaat om brandstof te besparen, krijg je minder schatten. Er is niet één enkel "beste" pad; er is een hele curve van "best mogelijke afwegingen". In de wiskunde wordt deze curve de Pareto-front genoemd.

Lama een tijd lang hadden computerwetenschappers een manier om deze curve perfect te vinden, maar het was alsof je elk individueel zandkorreltje op een strand probeerde te tellen om de perfecte plek voor een kasteel te vinden. Als het strand (het computermodel) te groot was, crashte de methode of duurde het eeuwig. Dit wordt de "state space explosion" genoemd.

Toen vonden ze een snellere manier uit genaamd Statistical Model Checking (SMC). In plaats van elk zandkorreltje te tellen, pak je gewoon een paar handvolnen willekeurig, meet ze, en gebruik je statistiek om te raden hoe het hele strand eruit ziet. Het is snel en werkt voor enorme stranden, maar tot nu toe kon het slechts één doel tegelijk controleren (bijv. "Hoeveel schatten kan ik krijgen?"). Het kon de lastige afweging tussen schat en brandstof niet aan.

Dit artikel introduceert een nieuwe methode om die "schat versus brandstof"-curve te vinden met behulp van de snelle, willekeurige steekproefmethode. Zo hebben ze het gedaan, met alledaagse analogieën:

1. De "Magische Dobbelsteen"-strategie (Lightweight Strategy Sampling)

Stel je voor dat je een gigantische bibliotheek hebt van elke mogelijke manier waarop je ruimteschip zou kunnen vliegen. Je kunt niet elk boek in de bibliotheek lezen. In plaats daarvan heb je een "Magische Dobbelsteen" (een hashfunctie).

Je gooit de dobbelsteen om een willekeurig vluchtplan (een "strategie") te kiezen.
Je simuleert dat vluchtplan op je computer om te zien hoeveel schat en brandstof het heeft gebruikt.
Omdat de dobbelsteen "lichtgewicht" is, kun je miljoens verschillende vluchtplannen kiezen zonder dat je een supercomputer nodig hebt om ze allemaal te onthouden. Je hebt alleen een klein briefje (een 32-bit getal) nodig om te onthouden welk plan je hebt gekozen.

2. De "Vertrouwensbox"

Wanneer je een vluchtplan simuleert, krijg je geen perfect getal; je krijgt een schatting met een beetje onzekerheid.

Denk aan dit als een box die rond je resultaat is getekend.
Het midden van de box is je beste gok.
De grootte van de box vertegenwoordigt hoe zeker je bent. Als je de simulatie 10 keer uitvoert, is de box klein. Als je hem één keer uitvoert, is de box enorm.
De wiskunde van dit artikel garandeert dat als je genoeg boxen tekent, de echte beste resultaten bijna zeker binnen deze boxen verborgen zitten.

3. De Curve Vinden (De Pareto-front)

De onderzoekers probeerden twee belangrijke manieren om de beste afwegingscurve te vinden met behruik van deze boxen:

Methode A: De "Eindeloze Ontdekkingsreiziger" (Incremental Sampling)
Stel je voor dat je een wandelaar bent die een bergketen probeert in kaart te brengen. Je stopt niet; je blijft gewoon lopen en tekent de kaart terwijl je gaat.

Je blijft willekeurige vluchtplannen kiezen en hun boxen tekenen.
Na verloop van tijd teken je een "vloer" (onderbenadering) en een "plafond" (bovenbenadering) rond de echte bergketen.
Terwijl je blijft wandelen, komen de vloer en het plafond dichter bij elkaar totdat ze de bergketen perfect omlijnen.
De Catch: Je moet eeuwig blijven wandelen om de perfecte omlijning te krijgen.

Methode B: De "Slimme Jager" (Fixed-Budget Algorithms)
Stel je voor dat je een beperkte hoeveelheid tijd hebt (bijv. 1 uur) om de beste plekken te vinden. Je kunt niet eeuwig wandelen, dus moet je slim zijn over waar je kijkt. Het artikel stelt drie "jachtstrategieën" voor:

Weight Vector Refinement: Je kiest een richting (bijv. "Ik geef meer om schat dan om brandstof"), vindt de beste plek voor die richting, verandert dan de richting iets en kijkt opnieuw. Je blijft de zoektocht verfijnen.
Fixed Iteration Budget: Je kiest een groep vluchtplannen, test ze, gooit de plannen weg die er slecht uitzien, en geeft de resterende tijd aan de "winnaars" om ze nauwkeuriger te testen.
Fixed Strategy Budget: Vergelijkbaar met hierboven, maar in plaats van de winnaars alleen maar nauwkeuriger te testen, voeg je nieuwe willekeurige vluchtplannen toe aan de mix terwijl je de winnaars test, zodat je geen verborgen parels mist.

Wat Hebben Ze Gevonden?

De auteurs bouwden een tool (genaamd modes) en testten deze op veel verschillende problemen, van het plannen van energie in een slim huis tot het navigeren van een onderzeeër in de diepe zee.

Het Goede Nieuws: Hun methode werkte op problemen die te groot waren voor de oude, perfecte methoden. Ze vonden goede afwegingscurves in seconden of minuten, terwijl de oude methoden uren zouden hebben geduurd of zouden zijn vastgelopen.
De "Simpele" Winnaar: Verrassend genoeg was de meest effectieve strategie vaak de simpelste: kies gewoon heel veel willekeurige vluchtplannen, gooi de plannen die duidelijk slecht zijn direct weg, en gebruik de resterende tijd om de rest uitgebreider te testen. Je hebt geen complexe wiskunde nodig om de slechte plannen te verwerpen; alleen naar de ruwe cijfers kijken was al genoeg.
De Beperking: Omdat ze gebruikmaken van willekeurige steekproeven, kunnen ze nooit 100% zeker zijn dat ze de absoluut perfecte curve hebben gevonden in een vaste hoeveelheid tijd. Ze kunnen alleen zeggen: "We zijn 95% zeker dat het echte antwoord binnen dit gebied ligt." Echter, voor massieve, complexe problemen is 95% zeker zijn veel beter dan niet in staat zijn het probleem überhaupt op te lossen.

Samenvattend

Dit artikel geeft ons een nieuwe manier om "pick your poison"-problemen (zoals snelheid versus veiligheid, of kosten versus kwaliteit) op te lossen voor gigantische computermodellen. In plaats van te proberen elke enkele mogelijkheid te berekenen (wat onmogelijk is voor grote systemen), gebruiken ze een slimme, willekeurige steekproeftechniek om een zeer nauwkeurige kaart te tekenen van de best mogelijke afwegingen, terwijl ze heel weinig computergeheugen gebruiken.

Technische Samenvatting: Multi-Objective Statistische Model Checking met Lichtgewicht Strategie-sampling

Probleemstelling

Statistische Model Checking (SMC) is een goed gevestigde techniek voor het verifiëren van probabilistische systemen met grote toestandsruimtes waar exhaustieve Probabilistische Model Checking (PMC) faalt door de explosie van de toestandsruimte. Echter, bestaande SMC-benaderingen zijn beperkt tot het evalueren van één eigenschap tegelijkertijd. In veel praktische scenario's, zoals het balanceren van het batterijverbruik van een satelliet tegenover het nut, of het optimaliseren van de kosten van een warmtepomp tegenover het comfort, hebben besluitvormers de Pareto-front nodig: de set van optimale afwegingen tussen meerdere, vaak conflicterende, doelstellingen.

Hoewel multi-objective PMC-algoritmen bestaan (bijv. met behulp van lineaire programmering of waarde-iteratie), vereisen deze volledige exploratie van de toestandsruimte, wat ze onbruikbaar maakt voor modellen met miljarden toestanden of hoogdimensionale doelruimtes. Bovendien behandelen bestaande tools zoals Uppaal Stratego multi-objective problemen alleen via lexicografische ordening of één-dimensionale optimalisatie, waardoor ze niet in staat zijn om afwegingen tussen doelstellingen met gelijke prioriteit te vangen. Er is momenteel geen SMC-benadering die in staat is om Pareto-fronten voor multi-objective queries te berekenen terwijl de constante geheugenvoetafdruk die kenmerkend is voor SMC behouden blijft.

Methodologie

Het artikel stelt de eerste SMC-benadering voor voor multi-objective Pareto-queries, gebouwd op Lightweight Strategy Sampling (LSS). De kernmethodologie bestaat uit de volgende componenten:

1. Lightweight Strategy Sampling (LSS)

Om de nondeterminisme in Markov Beslissingsprocessen (MDP's) te behandelen zonder informatie over de strategie per toestand op te slaan, maken de auteurs gebruik van LSS. In plaats van expliciet een strategie op te slaan, gebruikt LSS een compacte identifier (bijv. een 32-bit integer) en een hashfunctie om nondeterministische keuzes deterministisch op te lossen tijdens de simulatie. Dit maakt de simulatie van een groot aantal verschillende strategieën mogelijk met een constante hoeveelheid geheugen, onafhankelijk van de grootte van de toestandsruimte van het model.

2. Statistische Approximatie van de Pareto-front

De benadering samplet deterministische strategieën en evalueert deze via SMC om betrouwbaarheidsintervallen (CI's) voor elke doelstelling te verkrijgen.

Confidence Boxes: Voor een gesamplede strategie $\sigma$ produceert SMC een $d$ -dimensionale confidence box $B_\sigma$ rond de geschatte gemiddelde vector $\hat{x}_\sigma$ .
Under- en Overapproximatie: De convexe omhullende van de "meest pessimistische" hoeken van deze boxen vormt een kandidaat underapproximatie ( $\underline{C}$ ) van de bereikbare verzameling. Omgekeerd vormen de "meest optimistische" hoeken een kandidaat overapproximatie ( $\overline{C}$ ).
Multiple Comparisons: Om de gelijktijdige correctheid van alle confidence boxes met waarschijnlijkheid $\gamma$ te garanderen, passen de auteurs de Bonferroni-correctie (union bound) toe om het foutenbudget over de strategieën en dimensies te verdelen.

3. Algoritmen

Het artikel introduceert twee categorieën algoritmen:

A. Incrementele Sampling met Convergentie
Dit schema samplet onbeperkt batches van strategieën. Het past het foutenbudget per batch dynamisch aan (met behulp van een factor $f$ ) om te garanderen dat, in de limiet, de under- en overapproximaties convergeren naar een gelijktijdige confidence band rond de ware Pareto-front. Dit biedt een theoretische garantie van bijna zekere convergentie bij een ideale LSS.

B. Fixed-Budget Sampling
In het besef dat praktische toepassingen een eindige tijd hebben, worden drie heuristische algoritmen voorgesteld om de beste benadering te vinden binnen een vastgesteld simulatiebudget:

Weight Vector Refinement (WVR): Past multi-objective PMC-technieken toe door doelstellingen lineair te scalariseren. Het verfijnt iteratief gewichtsvectoren op basis van de afstand tussen de huidige approximaties en verwijdert suboptimale strategieën.
Fixed Iteration Budget (FIB): Samplet een initiële set strategieën en voert iteratief simulatieruns uit, waarbij de slechtst presterende strategieën in elke iteratie worden weggegooid om het budget te concentreren op veelbelovende kandidaten.
Fixed Strategy Budget (FSB): Vergelijkbaar met FIB, maar zorgt ervoor dat de uiteindelijke set overlevende strategieën een gelijk aantal simulatieruns ontvangt, waarbij nieuwe strategieën worden gesampled om de weggegooiden te vervangen.

Strategie Selectie Heuristieken:
Om strategieën te filteren, definiëren de auteurs verschillende regels gebaseerd op steekproefgemiddelden en betrouwbaarheidsintervallen (bijv. "Simple", "Far Enough", "Conservatively Far"). Deze regels bepalen of een strategie wordt gedomineerd door een andere met voldoende statistische zekerheid om te worden weggegooid.

Belangrijkste Bijdragen

Eerste Multi-Objective SMC: Het artikel presenteert het eerste SMC-framework dat in staat is om Pareto-fronten te benaderen voor $d$ doelstellingen met gelijke prioriteit.
Constante Geheugengebruik: De benadering behoudt het primaire voordeel van SMC: het geheugengebruik is constant ten opzichte van de grootte van de toestandsruimte van het model, wat de analyse van modellen met miljarden toestanden mogelijk maakt.
Statistische Garanties: Het incrementele schema biedt een theoretische garantie van convergentie naar een confidence band rond de ware Pareto-front. De fixed-budget algoritmen bieden statistisch verantwoorde ondergrenzen (underapproximaties) met een specifiek betrouwbaarheidsniveau.
Implementatie en Evaluatie: De technieken zijn geïmplementeerd in de modes simulator binnen de Modest Toolset. De auteurs evalueren de benadering op 40 benchmark-instanties uit de kwantitatieve verificatie en reinforcement learning literatuur, waarbij de resultaten worden vergeleken met de PMC-tool Storm.

Experimentele Resultaten

De experimenten tonen aan dat de voorgestelde SMC-benadering instanties kan afhandelen waar PMC-tools (Storm) falen door de explosie van de toestandsruimte of een timeout.

Schaalbaarheid: Voor grote modellen (bijv. fruit_tree met $2.7 \times 10^9$ toestanden, puddle_world varianten met honderden miljoenen toestanden), kan de SMC-benadering succesvol Pareto-front benaderingen berekenen in seconden tot minuten, terwijl PMC-tools een timeout gaven of niet konden voltooien.
Nauwkeurigheid: Voor kleinere modellen waar PMC-resultaten beschikbaar zijn, komen de SMC-approximaties vaak nauw overeen met de ware Pareto-front (bijv. deep_sea en fruit_tree modellen met een multiplicatieve $\epsilon$ dicht bij 1). De nauwkeurigheid varieert echter; voor sommige modellen zoals breakable_bottles kan de benadering verder van de ware front liggen, wat de stochastische aard van de sampling benadrukt.
Algoritme Prestaties: Onder de fixed-budget algoritmen leverde FSB (Fixed Strategy Budget) in combinatie met de Simple heuristiek en een configuratie die een hoog aantal initiële strategieën met minder runs per strategie bevoordeelt, over het algemeen de beste hypervolume-resultaten op.
Impact van Heuristieken: De "Simple" regel (het verwijderen van strategieën op basis van louter steekproefgemiddelden) presteerde vaak het best, wat suggereert dat het vroege verwijderen van niet-veelbelovende strategieën gunstig is in de geteste benchmark-set.

Betekenis en Claims

De auteurs beweren dat dit werk een kritieke kloof overbrugt tussen de schaalbaarheid van SMC en de complexiteit van multi-objective optimalisatie. Door gebruik te maken van lightweight strategy sampling, maakt de benadering de verificatie van afwegingen in systemen mogelijk die anders onbereikbaar zouden zijn voor exhaustieve methoden.

Het artikel erkent ook bescheiden beperkingen:

Overapproximatie: Hoewel het incrementele schema convergeert naar een confidence band, kunnen fixed-budget algoritmen in eindige tijd geen geldige overapproximatie garanderen omdat ze de optimale strategie volledig kunnen missen.
Strategieruimte: De methode gaat uit van een eindige strategieruimte (via vaste grootte identifiers). Hoewel dit praktisch is, is het een beperking vergeleken met de theoretisch oneindige ruimte van strategieën in algemene MDP's.
Modelklasse: Hoewel gedemonstreerd op MDP's, is de benadering direct toepasbaar op elke modelklasse die door LSS wordt ondersteund, zoals Markov automata en probabilistic timed automata, mits de runs bijna zeker termineren.

Het werk wordt gepresenteerd als een fundamentele stap, die een praktische tool biedt voor multi-objective verificatie in grootschalige systemen waar traditionele exhaustieve methoden niet beschikbaar zijn.