DSM-based variable ordering heuristic for reduced computational effort of symbolic supervisor synthesis

Research output: Contribution to journalConference articleAcademicpeer-review

1 Citation (Scopus)
44 Downloads (Pure)

Abstract

We consider the influence that the variable order of Binary Decision Diagrams (BDDs) has on the computational effort that is required for symbolic supervisor synthesis. In recent research it has been shown that improving the variable order can result in a substantial decrease of synthesis effort. We propose the combined use of the Dependency Structure Matrices (DSMs) and the matrix reordering heuristics Cuthill-McKee and Sloan to minimize the Weighted Event Span (WES) of the variable order. This is done by placing variables that often appear together in transition relations near each other. By performing benchmark experiments, we measure the reduction in synthesis effort by utilizing a variable order with minimized WES. The experiments show that our approach is competitive in reducing computational effort compared to FORCE, a state of practice variable ordering heuristic. Moreover, the best improvements in effort reduction are shown for the most computationally demanding models tested.
Original languageEnglish
Pages (from-to)429-436
Number of pages8
JournalIFAC-PapersOnLine
Volume53
Issue number4
DOIs
Publication statusPublished - 9 Nov 2020
Event15th International Workshop on Discrete Event Systems (WODES 2020) - Virtual, Rio de Janeiro, Brazil
Duration: 11 Nov 202013 Nov 2020
Conference number: 15

Keywords

  • Binary decision diagrams
  • Control system synthesis
  • Heuristic algorithms
  • Supervisory control
  • Variable order

Fingerprint

Dive into the research topics of 'DSM-based variable ordering heuristic for reduced computational effort of symbolic supervisor synthesis'. Together they form a unique fingerprint.

Cite this