3 - regelalgoritmen

Inleiding

De algoritmen die eerder behandeld zijn, zoals het bepalen van de som van twee getallen, het sorteren van een rij getallen, of het bepalen van de kortste route tussen twee punten, hebben alle een eindige invoer, een eindige rekentijd, en een eindig resultaat.

In dit hoofdstuk behandelen we een andere klasse van algoritmen: algoritmen voor het meten of regelen van een systeem. Dit soort algoritmen kom je tegen in de besturing van een machine of apparaat, of bij het bewaken van een bepaalde situatie (monitoring).

Monitoring

Bij monitoring gaat het om het meten van een (meestal continu) signaal, met als doel het bepalen van relevante eigenschappen en eventueel het signaleren van relevante gebeurtenissen. Voorbeelden:

brandalarm: als de concentraties van bepaalde gassen en rookdeeltjes en de temperatuur vooraf bepaalde grenswaarden overschrijden, wordt er een alarm gegeven naar de omgeving;
ECG (electrocardiogram, hartsignaal) monitoring, bijvoorbeeld op een intensive care: het electrocardiogram wordt continu gemeten, belangrijke eigenschappen zoals de hartslag worden bepaald, en bij een waarde die buiten het normale bereik ligt wordt alarm gegeven.
activiteitenmonitor: een activiteitenmonitor of slimme stappenteller houdt de lichamelijke activiteit, vooral lopen, gedurende de dag bij, en kan het resultaat toevoegen aan een globaal activiteiten-overzicht op het web.

Monitoring heeft niet noodzakelijk betrekking op het signaleren van een alarmsituatie; het kan bijvoorbeeld ook gaan om meetgegevens die elders gebruikt worden, of om het signaleren van de noodzaak van onderhoud.

Besturing

In het geval van besturing betreft het het bijsturen van een systeem in de richting van de gegeven doelstellingen, op grond van de doelstellingen en de gemeten waarden. Voorbeelden:

het regelen van de temperatuur van een oven: uitschakelen of lager schakelen van de verwarming als de temperatuur te hoog dreigt te worden, inschakelen of hoger schakelen van de verwarming als de temperatuur te laag dreigt te worden;
de besturing van een CD speler, bijvoorbeeld het besturen van de lade, en het bijsturen van de leeskop zodanig dat deze zich naar een gegeven track begeeft, en vervolgens het spoor volgt.

Bijgaande figuur beschrijft een systeem S dat geregeld wordt door een regelsysteem R. In dit geval bestuurt het regelsysteem de invoer van S op grond van een meting aan de uitvoer van S ("terugkoppeling"). Vaak is er sprake van een ingewikkelder vorm van besturing, en zijn er meerdere punten waarop het regelsysteem kan meten en ingrijpen.Tegenwoordig worden veel systemen bestuurd door een computersysteem met meerdere regelalgoritmen. Voorheen werden hiervoor vaak oplossingen op basis van analoge elektronica gebruikt, en daarvoor vaak mechanische systemen. Een klassiek voorbeeld van een mechanisch regelsysteem is de regulateur van James Watt, voor het limiteren van het toerental van zijn stoommachine; zie http://nl.wikipedia.org/wiki/Centrifugaalregelaar en http://en.wikipedia.org/wiki/Centrifugal_governor, of http://www.stoommachine.info/regulateur.html.) Dit is ook een voorbeeld van eenvoudige terugkoppeling.Het vakgebied van meet- en regeltechniek (control theory) heeft sinds die tijd een grote ontwikkeling doorgemaakt; zie bijvoorbeeld http://nl.wikipedia.org/wiki/Regeltechniek en http://en.wikipedia.org/wiki/Control_theory.

Voorbeelden uit het dagelijks leven

Enkele voorbeelden van regelalgoritmen uit de dagelijks leven, waarbij niet altijd computersystemen gebruikt worden:

verkeerslichtregeling: dit betreft een "discreet systeem", in die zin dat er een discreet aantal voertuigen het kruispunt passeert.
(logistiek/manufacturing) kanban (Zie http://nl.wikipedia.org/wiki/Kanban.)
thermostaat/temperatuurregeling: in de eenvoudigste vorm bestaat dit uit een regeling die de verwarming aan of uit zet op basis van een enkele temperatuursmeting; meer geavanceerde vormen gebruiken meerdere punten om de temperatuur te meten (binnen en buiten), waarbij de verwarming mogelijk harder of minder hard brandt ("modulerende ketel").

Enkele voorbeelden van regelsystemen waar tegenwoordig meestal (embedded) computersystemen voor gebruikt worden:

motormanagement bij auto's (o.a. regeling van ontsteking, inspuiting, e.d.)
lichtregeling in een kantoorgebouw (o.a. gebruik van sensoren om aanwezigheid van personen te detecteren)
regeling van verwarming en koeling van een gebouw
beveiliging van een spoorwegnet
besturing van een projectorlamp
besturing van een machine in een fabriek; besturing van een fabriek (logistiek e.d.)

Veel van dit soort regelsystemen zijn verborgen (embedded) in het apparaat dat bestuurd wordt, en daardoor vaak onzichtbaar voor de gebruiker van het apparaat.

Biologische regelsystemen

Ook in biologische systemen komen dergelijke regelmechanismen veel voor, bijvoorbeeld:

het regelen van de hartslag: bij grote inspanning moet het hart sneller slaan, bij rust minder. (De hartslag blijkt in rust overigens niet constant te zijn, maar enigszins te varieren.) Zie http://en.wikipedia.org/wiki/Heart_rate, http://en.wikipedia.org/wiki/Heart_rate_variability
het regelen van de bloedglucosespiegel: als deze te laag dreigt te worden, wordt er meer glucose vrijgemaakt, bijvoorbeeld door glucogeen, een polymeer van glucose, dat dient als buffer, om te zetten in glucose; als deze te hoog dreigt te worden, wordt er glucose omgezet in glycogeen.

Zie ook: http://nl.wikipedia.org/wiki/Bloedglucosespiegel; uit dit artikel:

Het hormoon insuline, geproduceerd door de eilandjes van Langerhans in de alvleesklier, stimuleert de opname van glucose in de cellen zodat de bloedglucosespiegel niet te hoog wordt. Verder zorgt insuline ervoor dat glucose dat teveel is in het bloed, in lever- en spiercellen omgezet wordt in glycogeen, zodat de bloedglucosespiegel zo weinig mogelijk schommelt. Het glycogeen wordt opgeslagen in die cellen, zodat het weer omgezet kan worden in glucose wanneer er een tekort is aan glucose in het bloed (glycogenolyse). Dat gebeurt onder andere onder invloed van de hormonen glucagon (ook geproduceerd door de eilandjes van Langerhans) en adrenaline. Ook kan het lichaam indien er te weinig glucose is, glucose maken via de gluconeogenese.

Het genoemde mechanisme voor het regelen van de bloedglucosespiegel kan misleid worden door bijvoorbeeld vlak voor een grote inspanning een grote hoeveelheid suiker in te nemen: het regelmechanisme reageert daarop door de bloedglucosespiegel te verlagen, wat in combinatie met de grote inspanning daarna, die ook bijdraagt aan een verlaging van de bloedglucosespiegel, tot een te laag niveau kan leiden.

Regelgoritmen in embedded systemen

Algoritmen voor monitoring en besturing met behulp van een computersysteem komen in de praktijk veel voor, maar meestal in een verborgen (embedded) vorm in een apparaat, zoals bijvoorbeeld een auto, een projectorlamp, een scheerapparaat, een televisie, een wasmachine, een magnetron, medische apparaten, enz.

Discretisatie

Bij het monitoren of besturen van een fysisch, chemisch of biologisch systeem moeten waarden (signalen) gemeten

en soms bijgestuurd worden. In de fysische realiteit zijn dit vaak analoge en continue signalen; in een computersysteem kunnen we alleen werken met discrete waarden (getallen). Dit betekent dat we moeten discretiseren: we meten de betreffende waarde op bepaalde tijdstippen (discretisatie in de tijd, bemonstering). De discretisatie in tijd wordt vaak uitgedrukt als frequentie (bemonsteringsfrequentie, sample frequency); we gebruiken daar vrijwel altijd een vaste periode.
we zetten de gemeten waarden om in een discreet waardenbereik (discretisatie van de waarde, kwantisatie). Bij discretisatie van de waarde wordt ook vaak een vaste (lineaire) verdeling gebruikt; het heeft soms voordelen om een logaritmische verdeling te gebruiken (met de grootste nauwkeurigheid rond 0).

Het resultaat is dat we een analoog, continu signaal omgezet hebben in een rij getallen.

Voor geluid (muziek-CD) gebruiken we bijvoorbeeld een bemonsteringsfrequentie van 44,1kHz , en een (lineaire) nauwkeurigheid van 16 bits. Deze waarden zijn overigens ingegeven door de gevoeligheid van het menselijk oor, meer dan door de eigenschappen van het oorspronkelijke muzieksignaal.

Door discretisatie benaderen we het oorspronkelijke signaal, en introduceren we een afwijking (fout) ten opzichte van het oorspronkelijke signaal. Deze afwijking is groter naarmate de bemonsteringsfrequentie lager is, en de nauwkeurigheid in het waardenbereik kleiner. Om ervoor te zorgen dat we het oorspronkelike signaal voldoende nauwkeurig kunnen benaderen, moeten we een bemonsteringsfrequentie en nauwkeurigheid kiezen die bij het oorspronkelijke signaal past.

Zie ook: http://en.wikipedia.org/wiki/Sampling_(signal_processing) (Het overeenkomstige item in de Nederlands Wikipedia is erg beperkt.)

Voor het omzetten van een continu signaal in discrete waarden wordt een zogenaamde analoog-digitaal omzetter (A/D converter) gebruikt; om weer een continu signaal terug te krijgen, bijvoorbeeld om dit als muziek af te spelen, gebruiken we een digitaal-analoog omzetter (D/A converter).

Een ander voorbeeld van discretisatie zien we bij film en video. In beide gevallen is er sprake van discretisatie in tijd: er wordt gewerkt met een beperkt aantal beelden per seconde. (Bij film: 24; bij video typisch 25, in Europa, 30, in de USA; zie en.wikipedia.org/wiki/Frame_rate ). In het geval van video vindt er ook nog discretisatie van de beelden zelf plaats: het beeld is verdeeld in discrete pixels, die bovendien een discrete kleur/helderheid hebben.

Opgave. we kunnen in plaats van 44,1 kHz en 16 bits, een geluidssignaal ook representeren met een veel hogere frequentie (typisch 2.8224 MHz, ofwel 64*44,1kHz) en een nauwkeurigheid van 1 bit. Leg uit hoe dit kan. (Zie ook http://en.wikipedia.org/wiki/Direct_Stream_Digital)

Leg uit waarom dit niet de andere kant op werkt, bijvoorbeeld halveren van de bemonsteringsfrequentie, en verdubbelen van de nauwkeurigheid per monster (sample).

Regelalgoritmen, real-time systemen

Typische eigenschappen van dit soort besturings- of regelalgoritmen zijn:

er is vaak sprake van een oneindige invoer, een niet-eindigende uitvoering (executie), en een oneindige uitvoer; de eindigheid wordt eerder bepaald door het apparaat of het gebruik van het apparaat, dan door het algoritme zelf;
bij besturing en monitoring speelt de reactietijd (latency) een rol; in veel gevallen moet de besturing binnen een maximale, voorgeschreven tijd reageren. In een aantal gevallen, bijvoorbeeld als er sprake is van interactie met mensen, moet deze reactietijd redelijk voorspelbaar zijn. Als er sprake is van dergelijke tijdseisen, spreken we over een real-time systeem.
een regelsysteem wordt vaak gebruikt om bijvoorbeeld de stabiliteit van het totale systeem te vergroten, of om te voorkomen dat het systeem in een niet-acceptabele toestand komt. Eigenschappen van het systeem, zoals stabiliteit, robuustheid, snelheid van aanpassing, zijn deels terug te voeren op eigenschappen van het besturingssysteem en de daarin gebruikte besturingsalgoritmen.

Bij een real-time systeem is het niet beslist noodzakelijk dat de reactietijd "zo kort mogelijk" is; de reactie moet op tijd zijn. Wat "op tijd" is, hangt erg af van de snelheid van het systeem dat bestuurd moet worden. Het mag duidelijk zijn dat een huishoudoven hier andere eisen stelt dan een straaljager.

Bij besturingsalgoritmen moeten vaak fysische (of chemische of biologische) grootheden gemeten en bestuurd worden, in plaats van abstracte informatie. Een goed begrip van het te besturen fysische, chemische of biologische systeem is essentieel. Modellering en soms ook simulatie spelen in dergelijke gevallen een belangrijke rol. In een volgend hoofdstuk gaan we daarop dieper in.

Voorbeeld : het vullen van een bak met water

Als voorbeeld van een regelalgoritme gebruiken we het vullen van een bak met water, door een stroom uit een kraan. Het doel is om een bepaalde hoogte van het water in de bak te bereiken, en vervolgens die hoogte te handhaven. Het handhaven van een bepaalde hoogte is triviaal als de bak niet lekt, maar we zullen ook het geval beschouwen van een bak die enigszins lekt. In eerste instantie gebruiken we een besturing die de kraan alleen kan openen en sluiten. Een mogelijke uitbreiding is om de grootte van de stroom door de kraan te kunnen regelen ("moduleren van de waterstroom").

Voor het eenvoudige geval, waarbij de besturing de kraan alleen kan openen en sluiten, krijgen we de volgende regels voor het besturingsalgoritme:

als de momentane hoogte < ingestelde hoogte: kraan open

als de momentane hoogte >= ingestelde hoogte: kraan dicht

Deze regels blijven geldig zolang de besturing ingeschakeld is; dit geldt in het bijzonder ook als de instelling van de gewenste hoogte verandert. We moeten dan mogelijk ook een mechanisme hebben om water weg te laten lopen, als de bak niet lek is.

Een meer geavanceerd besturingsalgoritme kunnen we gebruiken als we een kraan hebben waarvan we de stand kunnen continu (of in voldoend kleine stappen) kunnen regelen tussen helemaal dicht en helemaal open; we kunnen dan de waterstroom moduleren, in verhouding tot de hoeveelheid water die nog aan de bak toegevoegd moet worden.

In het bijgaande voorbeeld (waterbak-besturing) werken we deze regelingen verder uit.

Page updated

Google Sites

Report abuse