Related Experiment Video
Updated: Jul 7, 2026
08:35
Interactive and Visualized Online Experimentation System for Engineering Education and Research
Published on: November 24, 2021
On the complexity of supervisory control design in the RW framework
1Syst. Control Group, Toronto Univ., Ont.
Summary
Designing supervisory controls is computationally complex. It is unlikely to find efficient algorithms for concurrent systems or complex specifications, suggesting research into specialized cases for better performance.
Area of Science:
- Computer Science
- Control Theory
- Computational Complexity
Background:
- Supervisory control design is crucial for managing complex systems.
- Existing methods may face significant computational challenges.
- Understanding the inherent complexity is key to advancing the field.
Purpose of the Study:
- To analyze the time complexity of supervisory control design.
- To identify conditions under which efficient algorithms are unlikely.
- To guide future research toward more tractable problem instances.
Main Methods:
- Investigated the computational complexity of supervisory control synthesis.
- Analyzed the impact of concurrent plant components and intersecting specifications.
- Utilized concepts from computational complexity theory, explained for system engineers.
Main Results:
- Demonstrated that supervisory control design is generally intractable (exponential time complexity).
- Showed that complexity arises from concurrent components (m) and intersecting specifications (n).
- The state space size is typically exponential in m+n.
Conclusions:
- Efficient polynomial-time algorithms for general supervisory control are unlikely.
- Future research should focus on special cases with exploitable structural properties.
- This complexity analysis serves as a tutorial for system engineers new to computational complexity.
Related Concept Videos
01:10Control Systems
Control systems are everywhere in contemporary society, influencing diverse applications from aerospace to automated manufacturing. These systems can be found naturally within biological processes, such as blood sugar regulation and heart rate adjustment in response to stress, as well as in man-made systems like elevators and automated vehicles. A control system is essentially a network of subsystems and processes that collaboratively convert specific inputs into desired outputs.
At the heart...
At the heart...
01:26Feedback control systems
Feedback control systems are categorized in various ways based on their design, analysis, and signal types.
Linear feedback systems are theoretical models that simplify analysis and design. These systems operate under the principle that their output is directly proportional to their input within certain ranges. For instance, an amplifier in a control system behaves linearly as long as the input signal remains within a specific range. However, most physical systems exhibit inherent nonlinearity...
Linear feedback systems are theoretical models that simplify analysis and design. These systems operate under the principle that their output is directly proportional to their input within certain ranges. For instance, an amplifier in a control system behaves linearly as long as the input signal remains within a specific range. However, most physical systems exhibit inherent nonlinearity...
01:17Open and closed-loop control systems
Control systems are foundational elements in automation and engineering. They are broadly categorized into open-loop and closed-loop systems. These classifications hinge on the presence or absence of feedback mechanisms, significantly influencing the system's performance, complexity, and application.
An open-loop control system operates without feedback from the output. It consists of two primary elements: the controller and the controlled process. The controller receives an input signal and...
An open-loop control system operates without feedback from the output. It consists of two primary elements: the controller and the controlled process. The controller receives an input signal and...
01:22Controller Configurations
Controller configurations are crucial in a car's cruise control system because they manage speed over time to maintain a consistent pace regardless of road conditions, thereby meeting design goals. In traditional control systems, fixed-configuration design involves predetermined controller placement. System performance modifications are known as compensation.
Control-system compensation involves various configurations, most commonly series or cascade compensation, in which the controller aligns...
Control-system compensation involves various configurations, most commonly series or cascade compensation, in which the controller aligns...
01:25Control Systems: Applications
Electrical engineering plays a pivotal role in our daily lives, with control systems at the heart of many applications, from home appliances to sophisticated space shuttles. Control systems manage and regulate the behavior of devices and processes, ensuring they function safely, correctly, and efficiently.
In modern vehicles, control systems manage various functions to enhance performance and safety. The steering wheel and accelerator are primary inputs in a car's control system. The direction...
In modern vehicles, control systems manage various functions to enhance performance and safety. The steering wheel and accelerator are primary inputs in a car's control system. The direction...
01:18Hierarchy of Motor Control
The hierarchy of motor control refers to the different levels of organization and processing involved in controlling movement in the body. These levels range from higher cortical areas involved in planning and decision-making to lower spinal cord reflexes that respond automatically to external stimuli.