CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

A BDD-Based Approach for Designing Maximally Permissive Deadlock Avoidance Policies for Complex Resource Allocation Systems

Zhennan Fei (Institutionen för signaler och system, Automation) ; Spyros Reveliotis ; Knut Åkesson (Institutionen för signaler och system, Automation)
IEEE Transactions on Automation Science and Engineering (1545-5955). Vol. 12 (2015), 3, p. 990-1006.
[Artikel, refereegranskad vetenskaplig]

In order to develop a computationally efficient implementation of the maximally permissive deadlock avoidance policy (DAP) for complex resource allocation systems (RAS), a recent approach focuses on the identification of a set of critical states of the underlying RAS state-space, referred to as minimal boundary unsafe states. The availability of this information enables an expedient one-step-lookahead scheme that prevents the RAS from reaching outside its safe region. The work presented in this paper seeks to develop a symbolic approach, based on binary decision diagrams (BDDs), for efficiently retrieving the (minimal) boundary unsafe states from the underlying RAS state-space. The presented results clearly demonstrate that symbolic computation enables the deployment of the maximally permissive DAP for complex RAS with very large structure and state-spaces with limited time and memory requirements. Furthermore, the involved computational costs are substantially reduced through the pertinent exploitation of the special structure that exists in the considered problem.

Nyckelord: Binary decision diagrams; deadlock avoidance; discrete event systems; maximal permissiveness; resource allocation systems; supervisory control theory

Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2015-02-11. Senast ändrad 2015-08-21.
CPL Pubid: 212385


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för signaler och system, Automation


Robotteknik och automation

Chalmers infrastruktur