Abstrakt. Vi studerar problemet med kontrollantsyntes under budgetbegränsningar. I detta problem finns det en kostnad i samband med att göra en observation, och en kontrollant kan endast göra ett begränsat antal observationer i varje omgång så att den totala kostnaden för observationerna inte överstiger en given fast budget. Den personuppgiftsansvarige måste se till att det finns ett regelbundet krav som omfattas av budgetrestriktionerna. Budgetbegränsningar uppstår vid utformning och genomförande av styrenheter för resursbegränsade inbyggda system, där en styrenhet kanske inte har tillräckligt med kraft, tid eller bandbredd för att erhålla data från alla sensorer i varje omgång. De leder till spel med ofullständig information, där den okända informationen inte är fast a priori, men kan variera från runda till runda, baserat på de val som görs av den controllern hur man fördelar sin budget. Vi visar att det budgetbegränsade syntesproblemet för de reguljära målen är fullständigt under exponentiellt lång tid. Förutom att studera syntes under en fast budgetrestriktion studerar vi problemet med budgetoptimering, där vi med tanke på en anläggning, ett mål och observationskostnader måste hitta en controller som uppnår målet med minimal genomsnittlig ackumulerad kostnad (eller minimal toppkostnad). Vi visar att detta problem är reducible till ett spel av ofullständig information där det vinnande målet är en kombination av en.-regelbunden tillstånd och en långsiktig genomsnittlig tillstånd (eller minst max kostnad villkor), och detta leder återigen till en exponentiellt-tid algoritm. Slutligen utvidgar vi våra resultat till spel över oändliga statsrymder, och visar att det budgetbegränsade syntesproblemet är deciderbart för oändliga statsspel med stabila kvoter av finita index. Följaktligen är den diskreta tid budget-konstruerade syntes problem decidable för rektangulär hybrid automata.
Det finns några nyligen arbete med controller syntes med budget contraints där budgeten gäller i den långsiktiga REF.
Controller Synthesis with Budget Constraints
{'venue': 'HSCC', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}