Options
2023
Doctoral Thesis
Title
Reconfiguration of Hybrid Systems
Abstract
Hybrid systems are characterized by a combination of discrete and continuous behavior. Such hybrid systems are becoming more and more widespread, while constantly developing and growing in size because they create countless possibilities for modeling real-world systems. Let a tank, filled with water and connected to a sink through a binary valve, be a simple example; a model of such a system must follow the laws of fluid dynamics, representing the continuous aspect of the tank behavior, but the behavior also contains a discrete aspect, the binary valve. This tank, as all hybrid systems operating in the real-world are, is susceptible to faults, e.g., a crack in the casing creating a leak or a blockage in the valve. Such faults may lead to the system no longer behaving as desired and its control becoming invalid. In such cases, reconfiguration becomes necessary: the automated adaptation of a system to restore the desired behavior by exploiting redundancies in the system.
Reconfiguration has been in the scope of research on Artificial Intelligence (AI) for many years now. However, reconfiguration of hybrid systems is still an open research gap for several reasons. From the perspective of AI, the reconfiguration problems are typically solved using qualitative techniques such as search and logical reasoning, but continuous behavior and control are usually not considered. For practical applications, reconfiguration is often solved using naive search techniques or brute force. But as the number of discrete combinations rises exponentially with the number of options for adaptation, these approaches quickly come to their limitations. Hence, reconfiguration for hybrid systems requires dedicated and enhanced solution algorithms.
This thesis addresses this research gap with a new definition of reconfiguration for hybrid systems and two novel algorithms, which make use of the efficiency of AI approaches but also consider continuous aspects. The main contributions are as follows:
(i) A new definition of reconfiguration for hybrid systems is presented. This definition builds upon related definitions for reconfiguration of discrete systems from AI and extends these to also consider continuous characteristics. It thus forms the basis for the development of novel solution algorithms.
(ii) Two novel solution algorithms for reconfiguration of hybrid systems are presented. The first algorithm, AutoConf, is based on encoding the reconfiguration problem in propositional logic. It is applicable to partially observable systems and is very intuitive due to the use of logical calculi that mimic human reasoning. Furthermore, as it relies on well-established satisfiability solving, it allows for efficiently solving reconfiguration problems. For these reasons, AutoConf can be applied to a broad range of hybrid systems.
The second algorithm, BFReconf, is very explicit and directly operates on hybrid automata. It creates a problem representation in search and uses greedy best-first search to identify a solution. Even though the algorithm requires complete observability of the hybrid system, it rewards this with a clarity that allows for thorough theoretical examinations.
(iii) Soundness and completeness are formalized in the context of reconfiguration for hybrid systems for the first time. These properties allow about a formal and theoretical analysis of the effectiveness of a reconfiguration algorithm. Furthermore, the search-based algorithm BFReconf is shown to be sound and complete for stable, weakly-interconnected, linear hybrid systems.
(iv) Experimental evaluation shows the effectiveness of the presented algorithms in practical applications. It comprises experiments on representative simulations and real-world systems and examines statistical accuracy and runtime. The algorithms are shown to efficiently handle many reconfiguration scenarios. Furthermore, the runtimes of the algorithms are observed to often stay below an exponential blowup, which would usually appear when increasing the problem size.
To summarize, the presented formal definition of reconfiguration provides a basis for the development of reconfiguration approaches for hybrid systems. And indeed, two such approaches are formalized and shown to be capable of efficiently solving reconfiguration problems for representative systems. And thus, the presented work paves the way for hybrid systems to act autonomously and handle faults on their own.
Reconfiguration has been in the scope of research on Artificial Intelligence (AI) for many years now. However, reconfiguration of hybrid systems is still an open research gap for several reasons. From the perspective of AI, the reconfiguration problems are typically solved using qualitative techniques such as search and logical reasoning, but continuous behavior and control are usually not considered. For practical applications, reconfiguration is often solved using naive search techniques or brute force. But as the number of discrete combinations rises exponentially with the number of options for adaptation, these approaches quickly come to their limitations. Hence, reconfiguration for hybrid systems requires dedicated and enhanced solution algorithms.
This thesis addresses this research gap with a new definition of reconfiguration for hybrid systems and two novel algorithms, which make use of the efficiency of AI approaches but also consider continuous aspects. The main contributions are as follows:
(i) A new definition of reconfiguration for hybrid systems is presented. This definition builds upon related definitions for reconfiguration of discrete systems from AI and extends these to also consider continuous characteristics. It thus forms the basis for the development of novel solution algorithms.
(ii) Two novel solution algorithms for reconfiguration of hybrid systems are presented. The first algorithm, AutoConf, is based on encoding the reconfiguration problem in propositional logic. It is applicable to partially observable systems and is very intuitive due to the use of logical calculi that mimic human reasoning. Furthermore, as it relies on well-established satisfiability solving, it allows for efficiently solving reconfiguration problems. For these reasons, AutoConf can be applied to a broad range of hybrid systems.
The second algorithm, BFReconf, is very explicit and directly operates on hybrid automata. It creates a problem representation in search and uses greedy best-first search to identify a solution. Even though the algorithm requires complete observability of the hybrid system, it rewards this with a clarity that allows for thorough theoretical examinations.
(iii) Soundness and completeness are formalized in the context of reconfiguration for hybrid systems for the first time. These properties allow about a formal and theoretical analysis of the effectiveness of a reconfiguration algorithm. Furthermore, the search-based algorithm BFReconf is shown to be sound and complete for stable, weakly-interconnected, linear hybrid systems.
(iv) Experimental evaluation shows the effectiveness of the presented algorithms in practical applications. It comprises experiments on representative simulations and real-world systems and examines statistical accuracy and runtime. The algorithms are shown to efficiently handle many reconfiguration scenarios. Furthermore, the runtimes of the algorithms are observed to often stay below an exponential blowup, which would usually appear when increasing the problem size.
To summarize, the presented formal definition of reconfiguration provides a basis for the development of reconfiguration approaches for hybrid systems. And indeed, two such approaches are formalized and shown to be capable of efficiently solving reconfiguration problems for representative systems. And thus, the presented work paves the way for hybrid systems to act autonomously and handle faults on their own.
;
Hybride Systeme zeichnen sich durch diskretes und kontinuierliches Verhalten aus. Solch hybride Systeme sind immer verbreiteter und werden gleichzeitig immer größer, da sie zahlreiche Möglichkeiten zur Modellierung von Echt-Welt-Systemen bieten. Zum Beispiel ein Tank, der mit Wasser gefüllt und mit einem binären Ventil verbunden ist, unterliegt den Gesetzen der Fluiddynamik, weist durch die verschiedenen Öffnungsmodi des binären Ventils allerdings auch diskrete Charakteristiken auf. Dieser Tank ist, wie alle Echt-Welt-Systeme, anfällig für Fehler, zum Beispiel einen Riss in der Hülle, der zu einem Leck führt, oder ein blockierendes Ventil. Solche Fehler können dazu führen, dass das System sich nicht mehr wie gewünscht verhält und die Regelung des Systems ungültig wird. In derartigen Fällen wird Rekonfiguration erforderlich: Rekonfiguration beschreibt die automatische Adaption eines Systems durch das Ausnutzen von Redundanzen, um gewünschtes Systemverhalten wiederherzustellen.
Rekonfiguration ist schon seit vielen Jahren in den Bereichen Künstliche Intelligenz (KI) im Fokus der Forschung. Für hybride Systeme ist Rekonfiguration allerdings aus verschiedenen Gründen eine noch offene Forschungslücke. Im Bereich der KI werden Rekonfigurationsprobleme mittels qualitativer Techniken wie zum Beispiel Suchverfahren und logischem Schließen gelöst; kontinuierliches Verhalten und Regelung werden üblicherweise nicht berücksichtigt. Für praktische Anwendungen wird Rekonfiguration oft mittels naiver Suchverfahren oder Brute-Force-Methoden gelöst. Da allerdings die Anzahl diskreter Kombinationen exponentiell mit der Anzahl der Adaptionsmöglichkeiten steigt, kommen diese Verfahren schnell an ihre Grenzen. Von daher benötigt die Rekonfiguration hybrider Systeme erweiterte Lösungsverfahren.
In der vorliegenden Arbeit wird diese Forschungslücke adressiert. Eine neue Definition von Rekonfiguration für hybride Systeme und zwei neue Algorithmen, die die Effizienz von KI-Techniken ausnutzen, aber auch kontinuierliche Aspekte berücksichtigen, werden vorgestellt. Die Hauptbeiträge sind wie folgt:
(i) Eine neue Definition von Rekonfiguration für hybride Systeme wird vorgestellt. Diese Definition setzt auf verwandte Definitionen für Rekonfiguration diskreter Systeme aus der KI auf und erweitert diese, um auch kontinuierliche Charakteristiken abzubilden. Sie bildet somit die Basis für die Entwicklung neuer Rekonfigurationsalgorithmen.
(ii) Zwei neue Lösungsalgorithmen für die Rekonfiguration hybrider Systeme werden vorgestellt. Der erste Algorithmus, AutoConf, basiert auf einer Formulierung in Aussagenlogik. Er ist auf teilweise beobachtbare Systeme anwendbar und ist durch den Einsatz eines logischen Kalküls, das menschliches Schließen imitiert, sehr intuitiv. Somit kann er auf ein breites Spektrum hybrider Systeme angewandt werden. Da der Algorithmus darüber hinaus auf die Lösung eines Erfüllbarkeitsproblems zurückgreift, für das es ausgereifte Solver gibt, ermöglicht er das effiziente Lösen von Rekonfigurationsproblemen.
Der zweite Algorithmus, BFReconf, ist sehr explizit und arbeitet direkt auf hybriden Automaten. Er erstellt eine Problemrepräsentation in Form eines Suchraums und nutzt gierige Bestensuche, um eine Lösung zu identifizieren. Der Algorithmus erfordert zwar die vollständige Beobachtbarkeit des hybriden Automaten, belohnt diese allerdings mit einer Klarheit, die ausgiebige theoretische Analysen ermöglicht.
(iii) Zum ersten Mal werden Korrektheit und Vollständigkeit im Kontext von Rekonfiguration hybrider Systeme formalisiert. Diese Eigenschaften ermöglichen es, theoretische Aussagen über die Effektivität eines Rekonfigurationsalgorithmus zu treffen. Außerdem wird gezeigt, dass der auf der Suche basierende Algorithmus BFReconf für stabile, schwach verbundene, lineare hybride Systeme korrekt und vollständig ist.
(iv) Eine experimentelle Evaluation zeigt die Effektivität der vorgestellten Ansätze für praktische Anwendungen. Sie umfasst Experimente mit repräsentativen Simulationen und Echt-Welt-Systemen und untersucht sowohl die statistische Genauigkeit als auch die Laufzeit der Verfahren. Es wird gezeigt, dass die Algorithmen viele Szenarien effizient lösen. Außerdem bleiben die Laufzeiten der Algorithmen oft unter einer exponentiellen Laufzeitexplosion, die üblicherweise bei der Erhöhung der Problemgröße zu erwarten wäre.
Zusammengefasst bildet die neue, formale Definition von Rekonfiguration für hybride Systeme die Grundlage für die Entwicklung neuer Rekonfigurationsansätze. Zwei solcher neuen Ansätze werden in dieser Arbeit vorgestellt. Es wird gezeigt, dass diese Ansätze in der Lage sind, Rekonfigurationsprobleme für repräsentative Systeme effizient zu lösen. Dadurch werden die Fähigkeiten hybrider Systeme, autonom zu agieren und auf Fehler selbstständig zu reagieren, erhöht.
Rekonfiguration ist schon seit vielen Jahren in den Bereichen Künstliche Intelligenz (KI) im Fokus der Forschung. Für hybride Systeme ist Rekonfiguration allerdings aus verschiedenen Gründen eine noch offene Forschungslücke. Im Bereich der KI werden Rekonfigurationsprobleme mittels qualitativer Techniken wie zum Beispiel Suchverfahren und logischem Schließen gelöst; kontinuierliches Verhalten und Regelung werden üblicherweise nicht berücksichtigt. Für praktische Anwendungen wird Rekonfiguration oft mittels naiver Suchverfahren oder Brute-Force-Methoden gelöst. Da allerdings die Anzahl diskreter Kombinationen exponentiell mit der Anzahl der Adaptionsmöglichkeiten steigt, kommen diese Verfahren schnell an ihre Grenzen. Von daher benötigt die Rekonfiguration hybrider Systeme erweiterte Lösungsverfahren.
In der vorliegenden Arbeit wird diese Forschungslücke adressiert. Eine neue Definition von Rekonfiguration für hybride Systeme und zwei neue Algorithmen, die die Effizienz von KI-Techniken ausnutzen, aber auch kontinuierliche Aspekte berücksichtigen, werden vorgestellt. Die Hauptbeiträge sind wie folgt:
(i) Eine neue Definition von Rekonfiguration für hybride Systeme wird vorgestellt. Diese Definition setzt auf verwandte Definitionen für Rekonfiguration diskreter Systeme aus der KI auf und erweitert diese, um auch kontinuierliche Charakteristiken abzubilden. Sie bildet somit die Basis für die Entwicklung neuer Rekonfigurationsalgorithmen.
(ii) Zwei neue Lösungsalgorithmen für die Rekonfiguration hybrider Systeme werden vorgestellt. Der erste Algorithmus, AutoConf, basiert auf einer Formulierung in Aussagenlogik. Er ist auf teilweise beobachtbare Systeme anwendbar und ist durch den Einsatz eines logischen Kalküls, das menschliches Schließen imitiert, sehr intuitiv. Somit kann er auf ein breites Spektrum hybrider Systeme angewandt werden. Da der Algorithmus darüber hinaus auf die Lösung eines Erfüllbarkeitsproblems zurückgreift, für das es ausgereifte Solver gibt, ermöglicht er das effiziente Lösen von Rekonfigurationsproblemen.
Der zweite Algorithmus, BFReconf, ist sehr explizit und arbeitet direkt auf hybriden Automaten. Er erstellt eine Problemrepräsentation in Form eines Suchraums und nutzt gierige Bestensuche, um eine Lösung zu identifizieren. Der Algorithmus erfordert zwar die vollständige Beobachtbarkeit des hybriden Automaten, belohnt diese allerdings mit einer Klarheit, die ausgiebige theoretische Analysen ermöglicht.
(iii) Zum ersten Mal werden Korrektheit und Vollständigkeit im Kontext von Rekonfiguration hybrider Systeme formalisiert. Diese Eigenschaften ermöglichen es, theoretische Aussagen über die Effektivität eines Rekonfigurationsalgorithmus zu treffen. Außerdem wird gezeigt, dass der auf der Suche basierende Algorithmus BFReconf für stabile, schwach verbundene, lineare hybride Systeme korrekt und vollständig ist.
(iv) Eine experimentelle Evaluation zeigt die Effektivität der vorgestellten Ansätze für praktische Anwendungen. Sie umfasst Experimente mit repräsentativen Simulationen und Echt-Welt-Systemen und untersucht sowohl die statistische Genauigkeit als auch die Laufzeit der Verfahren. Es wird gezeigt, dass die Algorithmen viele Szenarien effizient lösen. Außerdem bleiben die Laufzeiten der Algorithmen oft unter einer exponentiellen Laufzeitexplosion, die üblicherweise bei der Erhöhung der Problemgröße zu erwarten wäre.
Zusammengefasst bildet die neue, formale Definition von Rekonfiguration für hybride Systeme die Grundlage für die Entwicklung neuer Rekonfigurationsansätze. Zwei solcher neuen Ansätze werden in dieser Arbeit vorgestellt. Es wird gezeigt, dass diese Ansätze in der Lage sind, Rekonfigurationsprobleme für repräsentative Systeme effizient zu lösen. Dadurch werden die Fähigkeiten hybrider Systeme, autonom zu agieren und auf Fehler selbstständig zu reagieren, erhöht.
Thesis Note
Hamburg, Univ., Diss., 2023