Active Diagnosis with Costs and Rewards
Serge Haddad, Engel Lefaucheux, Stefan Schwoon
Diagnosis is the task of detecting fault occurrences in a partially observed system. Depending on the possible observations, a discrete-event system may be diagnosable or not. Active diagnosis aims at controlling the system to render it diagnosable. In the past, the main analyzed criteria of the quality of an active diagnoser has been the delay between the fault occurrence and its de- tection. Here we generalize this study by (1) associating costs or rewards with faulty runs, (2) defining three related decision problems, and (3) analyzing their decidability/complexity in the non-deterministic and probabilistic frameworks under several hypotheses. We compare non-deterministic and probabilistic se- mantics and show that for most of the problems their decidability and complex- ity coincide. Nonetheless we exhibit one problem decidable for non-deterministic systems but undecidable for probabilistic ones. Furthermore we establish tight lower annd upper bounds for the memory size of the active diagnoser (when it exists).