A greedy algorithm for computing finite-makespan controllable sublanguages
The Ramadge-Wonham supervisory control paradigm has been shown effective in dealing with logic control. Nevertheless, time-related performance is always one of the major concerns in industry. Recently, a new time optimal control framework has been proposed, and an algorithm for synthesizing a minimu...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Language: | English |
| Published: |
2013
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/84659 http://hdl.handle.net/10220/12502 |
| _version_ | 1826120390257147904 |
|---|---|
| author | Su, Rong. |
| author2 | School of Electrical and Electronic Engineering |
| author_facet | School of Electrical and Electronic Engineering Su, Rong. |
| author_sort | Su, Rong. |
| collection | NTU |
| description | The Ramadge-Wonham supervisory control paradigm has been shown effective in dealing with logic control. Nevertheless, time-related performance is always one of the major concerns in industry. Recently, a new time optimal control framework has been proposed, and an algorithm for synthesizing a minimum-makespan controllable sublanguage has been provided. But it has been shown that computing such a minimum-makespan controllable sublanguage is NP-hard. To avoid this complexity issue, we present a polynomial-time algorithm that computes a finite-makespan controllable sublanguage. To evaluate the potential difference between the attained finite makespan and the actual minimum makespan, we provide a polynomial-time algorithm to compute a strictly lower bound of the minimum makespan so that explicitly computing such a minimum makespan can be avoided. Experimental results are provided to show the effectiveness of our algorithms. |
| first_indexed | 2024-10-01T05:15:59Z |
| format | Conference Paper |
| id | ntu-10356/84659 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T05:15:59Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | ntu-10356/846592020-03-07T13:24:45Z A greedy algorithm for computing finite-makespan controllable sublanguages Su, Rong. School of Electrical and Electronic Engineering IEEE Annual Conference on Decision and Control (51st : 2012 : Maui, Hawaii, US) DRNTU::Engineering::Electrical and electronic engineering The Ramadge-Wonham supervisory control paradigm has been shown effective in dealing with logic control. Nevertheless, time-related performance is always one of the major concerns in industry. Recently, a new time optimal control framework has been proposed, and an algorithm for synthesizing a minimum-makespan controllable sublanguage has been provided. But it has been shown that computing such a minimum-makespan controllable sublanguage is NP-hard. To avoid this complexity issue, we present a polynomial-time algorithm that computes a finite-makespan controllable sublanguage. To evaluate the potential difference between the attained finite makespan and the actual minimum makespan, we provide a polynomial-time algorithm to compute a strictly lower bound of the minimum makespan so that explicitly computing such a minimum makespan can be avoided. Experimental results are provided to show the effectiveness of our algorithms. 2013-07-29T08:38:01Z 2019-12-06T15:49:00Z 2013-07-29T08:38:01Z 2019-12-06T15:49:00Z 2012 2012 Conference Paper Su, R. (2012). A greedy algorithm for computing finite-makespan controllable sublanguages . 2012 IEEE 51st IEEE Conference on Decision and Control (CDC). https://hdl.handle.net/10356/84659 http://hdl.handle.net/10220/12502 10.1109/CDC.2012.6426912 en © 2012 IEEE. |
| spellingShingle | DRNTU::Engineering::Electrical and electronic engineering Su, Rong. A greedy algorithm for computing finite-makespan controllable sublanguages |
| title | A greedy algorithm for computing finite-makespan controllable sublanguages |
| title_full | A greedy algorithm for computing finite-makespan controllable sublanguages |
| title_fullStr | A greedy algorithm for computing finite-makespan controllable sublanguages |
| title_full_unstemmed | A greedy algorithm for computing finite-makespan controllable sublanguages |
| title_short | A greedy algorithm for computing finite-makespan controllable sublanguages |
| title_sort | greedy algorithm for computing finite makespan controllable sublanguages |
| topic | DRNTU::Engineering::Electrical and electronic engineering |
| url | https://hdl.handle.net/10356/84659 http://hdl.handle.net/10220/12502 |
| work_keys_str_mv | AT surong agreedyalgorithmforcomputingfinitemakespancontrollablesublanguages AT surong greedyalgorithmforcomputingfinitemakespancontrollablesublanguages |