FaultDiagnosis.cc

Go to the documentation of this file.

#include <map>


#include <unordered_map>
#include <unordered_set>
#include <utils/MyTime.hh>
#include <FaultDiagnosis.hh>
        

namespace Diades
{
  namespace Automata
  {

        /*****************************************************************************************************/
        
        FaultDiagnosis::FaultDiagnosis(const vector<const ObservableComponent *> models,
                                                                   const SynchronisationRules & rules,
                                                                   const set<Event> & faults):
          _type(Comp),_faultEvents(faults),
          _globalModel(0),_diagnoser(0),_globalComposableModel(0),
          _currentState(0),
          _currentFaults(0),_currentGlobalStates()
        {
          // initialisation of the diagnosis. The belief state is the product of the initial states
          // of the components. BE CAREFUL, THE ALGORITHM IS ENUMERATIVE SO IT WONT WORK FOR VERY
          // BIG SETS. @todo BE SYMBOLIC !!!
          _currentState = new list< vector<State> >;
          _currentFaults = new list< set<Event> >;
          vector<ObservableComponent::InitialStateIterator> its(_models.size());
          bool finished = false;

          for(unsigned i = 0; i < models.size(); ++i)
                {
                  its[i] = models[i]->initialStateBegin();
                  finished = finished
                        ||
                        ( models[i]->initialStateBegin() ==  models[i]->initialStateEnd());
                }

          while(!finished)
                 {
                   _currentState->push_back(vector<State>(_models.size()));
                   _currentFaults->push_back(set<Event>());
                   for(unsigned i = 0; i < _models.size(); ++i)
                         {
                           _currentState->back().operator[](i) = *its[i];
                         }
                   ++its[0];
                   unsigned j = 0;
                   while((j < (_models.size() - 1))
                                 &&
                                 (its[j] == _models[j]->endOfInitialStates()))
                         {
                           its[j] = _models[j]->beginOfInitialStates();
                           ++j;
                           ++its[j];
                         }
                   finished =
                         (its[_models.size() - 1] == _models[_models.size() - 1]->endOfInitialStates());
                 }
          // Now let initialize the ComposableModel from which we will retrieve the global model
          // transitions on the fly.
          for(unsigned i = 0; i < models.size(); ++i)
                {
                  _models.push_back(new ComposableModel(*models[i],rules));
                }

          // Now the implicit global model
          _globalComposableModel = new ComposableModel(_models,rules,true);
          
          
        }
        
        
        /*****************************************************************************************************/


        FaultDiagnosis::FaultDiagnosis(ClassicalDiagnoser & diagnoser):
          _type(Diagnoser),_faultEvents(),
          _globalModel(0),_diagnoser(&diagnoser),_models(0),_globalComposableModel(0),_rules(0),
          _currentState(0),
          _currentFaults(0),_currentGlobalStates()
        {
          require(Exception,diagnoser.valid(),"FaultDiagnosis::constructor: invalid diagnoser");
          _faultEvents.insert(diagnoser.beginOfDiagnosedEvents(),
                                                  diagnoser.endOfDiagnosedEvents());
          // initialisation of the diagnosis. The belief state is the set of initial states
          // contained in the diagnoser. The data structure _currentState and _currentFaults
          // are not used in this algorithm as it would be totally redundant with the diagnoser
          _diagnoser->initialize();
        }

        
        /*****************************************************************************************************/

        FaultDiagnosis::FaultDiagnosis(const ObservableComponent & globalModel, const set<Event> & faults):
          _type(Global),_faultEvents(faults),
          _globalModel(&globalModel),_diagnoser(0),_models(0), _globalComposableModel(0),_rules(0),
          _currentState(0),
          _currentFaults(0),_currentGlobalStates()
        {
          require(Exception,globalModel.valid(),"FaultDiagnosis::constructor: invalid global model");
          require(Exception,!faults.empty(),"FaultDiagnosis::constructor: no fault");
         
          _currentState = new list< vector<State> >;
          _currentFaults = new list< set<Event> >;
          // initialisation of the diagnosis. The belief state is the set of initial states
          // of the global model
          // note that for genericity reasons a state is declared as a vector of State (for component-based
          // algorithms). Here a state is in a vector of size 1.
          for(ObservableComponent::InitialStateIterator it = globalModel.initialStateBegin();
                  it != globalModel.initialStateEnd();
                  ++it)
                {
                  vector<State> globalState(1);
                  globalState[0] = *it;
                  _currentState->push_back(globalState);
                  _currentFaults->push_back(set<Event>());
                  
                }
          // ok so here _currentState contains the initial belief state according to the model 'globalModel'
          // and for each state we say that no fault has occurred (in _currentFaults).
          // for efficieny purpose, _currentGlobalStates will also contain the belief state
          _currentGlobalStates.insert(globalModel.initialStateBegin(), globalModel.initialStateEnd());
          
        }
        
        
        /*****************************************************************************************************/
        
        void FaultDiagnosis::getDiagnosis(Diagnosis & diagnosis)
        {
          

          switch(_type)
                {
                case Global:
                  {
                        require(Exception,!_currentState->empty(), "FaultDiagnosis::printDiagnosis The diagnosis is empty");
          require(Exception,_currentFaults->size() == _currentState->size(), "FaultDiagnosis::printDiagnosis The diagnosis is not correctly set");
                        list< vector<State> >::const_iterator currentStateIt = _currentState->begin();
                        list< set<Event> >::const_iterator currentFaultsIt = _currentFaults->begin();
                        while((currentStateIt != _currentState->end())
                                  &&
                                  (currentFaultsIt != _currentFaults->end()))
                          {
                                vector<Diades::Graph::NodeId> state;
                                state.push_back(currentStateIt->front().id());
                                vector< set<Event> > faults;
                                faults.push_back(*currentFaultsIt);
                                diagnosis.addCandidate(Candidate(state,faults));
                                ++currentFaultsIt;
                                ++currentStateIt;
                          }
                  }
                  break;
                case Diagnoser:
                  {
                        _diagnoser->getDiagnosis(diagnosis);
                  }
                  break;
                default:
                  {
                        cout << "UNKNOWN ALGORITHM" << endl;
                  }
                }
        }


        /*****************************************************************************************************/

        void FaultDiagnosis::diagnose(const Event & obs)
        {
          // so, this method is in charge of diagnosing independently
          // of the underlying algorithm.
          switch(_type)
                {
                case Global:
                  {
                        globalModelDiagnose(obs);
                        break;
                  }
                case Diagnoser:
                  {
                        diagnoserDiagnose(obs);
                        break;
                  }
                case Comp:
                  {
                        componentDiagnose(obs);
                        break;
                  }
                default:
                  {
                        cout << "HEY MAN, I ALREADY TOLD YOU IT WAS NOT IMPLEMENTED" << endl;
                  }
                }
        }
        /********************************************************************************************/

        void FaultDiagnosis::componentDiagnose(const Event & obs)
        {
          // this method is in charge of diagnosing 'label'
          // with a naive search (BFS) on the global model


          // this structure is in charge of saving the results
          // By observing 'label' from one initial state one may reach
          // a set of states. And to reach them, it may be possible
          // that fault events occur
          unordered_map< State,  list<  pair<State,set<Event> > > > solutions;


          // the state space is (model state x faults)
          // during the search we need to know the state of the model AND
          // the set of faults that can occur before reaching this state.
          list< pair<State,set<Event> > > visitingStates;
        
          // here, i will store model states which I found out that no future
          // trajectory can emit the observation 'label'
          // a state in "noSolutions" means that the previous diagnosis is refined
          // any candidate in noSolutions is incompatible with the new observation.
          set<State> noSolutions;
          bool thereIsSolution = false;
        
          // loop on the current belief state
          for(set<State>::const_iterator stateIt = _currentGlobalStates.begin();
                  stateIt != _currentGlobalStates.end();
                  ++stateIt)
                {
                  // just to avoid visiting states an infinite number of time, one is enough
                  unordered_multimap< State , set<Event> > visitedOrVisitingStates;

                  // feel lucky, otherwise i put the current state in the queue and tag it
                  // as  visitedOrVisiting to avoid to put it again in the queue afterwards.
                  if(noSolutions.find(*stateIt) == noSolutions.end())
                        {
                          visitingStates.push_back( make_pair(*stateIt, set<Event>()) );        
                          visitedOrVisitingStates.insert(visitingStates.back());
                        }

                  // as long as the queue is not empty, there are states to visit
                  while(!visitingStates.empty())
                        {
                          // current model state
                          State & currentState = visitingStates.front().first;
                          // current set of fault that has occured before 'currentState'
                          set<Event> & currentFaults =  visitingStates.front().second;
                        
                        
                        
                          bool noSolutionForThisState = true;
                          // let's have a look at the successors of the currentState
                          for(ObservableComponent::OutputTransitionIterator outTransIt = _globalModel->outputTransitionBegin(currentState);
                                  outTransIt != _globalModel->outputTransitionEnd(currentState); ++outTransIt)
                                {
                                  if(_globalModel->getEvent(*outTransIt) == obs)
                                        { 
                                          // good, a transition is labeled with 'obs' so the target is a solution
                                          thereIsSolution = true;
                                          noSolutionForThisState = false;
                                          // so, from *stateIt, by observing 'obs', we can reach 'outTransIt->target()' and
                                          // 'currentFaults' has occurred during the trip
                                          solutions[*stateIt].push_back(make_pair(outTransIt->target(), currentFaults) );
                                        }                       
                                  else
                                        {
                                          // no luck, it is not obs :-(
 

                                          if(!_globalModel->mask().isObservable(_globalModel->getEvent(*outTransIt)))
                                                {
                                                  // seems this transition is not observable 
                                                  // so we need to explore its successors...
                                                   
                                                  if(noSolutions.find(outTransIt->target()) == noSolutions.end())
                                                        {
                                                          // the target of the transition is not registered as a "no solution state"
                                                          // so  we need to explore its successors...
                                                          noSolutionForThisState = false;
                                                          set<Event> newCurrentFaults = currentFaults;
                                                         
                                                          if(_faultEvents.find(_globalModel->getEvent(*outTransIt)) != _faultEvents.end())
                                                                {
                                                                  // the visited transitions trigger a fault, we need to keep trace of it!
                                                                  
                                                                  newCurrentFaults.insert(_globalModel->getEvent(*outTransIt));
                                                                }

                                                          //ok now we need to explore the state (outTransIt->target(), newCurrentFaults)
                                                          // but it may already be in the queue, let's have a look....
                                                          typedef unordered_multimap <State, set<Event> >::const_iterator MapIterator; 
                                                          pair< MapIterator, MapIterator > range = visitedOrVisitingStates.equal_range(outTransIt->target());
                                                          
                                                          bool found = false;
                                                          MapIterator visitedIt = range.first;
                                                          while( (!found) && (visitedIt != range.second) )
                                                                {
                                                                  found = visitedIt->second == newCurrentFaults;
                                                                  ++visitedIt;
                                                                }       
                                                          
                                                          if(!found)
                                                                {
                                                                  // the state (outTransIt->target(), newCurrentFaults) is not in the queue,
                                                                  // need to add it in the end (that is a BFS)
                                                                  visitingStates.push_back(make_pair(outTransIt->target(),newCurrentFaults));
                                                                  visitedOrVisitingStates.insert(visitingStates.back()); 
                                                                }
                                                        }
                                                }
                                        }
                                }
                          if(noSolutionForThisState)
                                {
                                  // from current state, we have not found any trajectory that
                                  // emit the observation 'obs'. Let us  save this information somewhere
                                  // as it may help for further search...
                                  noSolutions.insert(currentState); 
                                }
                          // finally current_state has been visited, let us handle the next state in the queue....
                          visitingStates.pop_front();
                        }
                }
        
          if(!thereIsSolution)
                {
                  // this is the worst case ever, it should never happen with the hypotheses we took for pj work.
                  // anyway, code is never perfect, just for debugging...
                  cout << "No solution found for the following problem" << endl;
                  cout << "Observation = " << obs.label() << endl;
                  cout << "Previous Diagnosis = " << endl;
                  Diagnosis diagnosis;
                  getDiagnosis(diagnosis);
                  cout << diagnosis << endl;
                }       
        
          // let us update the diagnosis now!
          // don't forget that the table solutions contains the result of the search
          // between the initial beliefstate and the new belief state with
          // a record of the fault event that has occurred during this search
          // now we need to 'append' this table with the previous diagnosis
          // by updating the past set of faults with the new ones....



          // will put the new belief state here
          _currentGlobalStates.clear();

          // let save the previous belief state temporally
          list< vector<State> > * previousCurrentState  = _currentState;
          list< set<Event> > * previousCurrentFaults = _currentFaults;

          // and create new structures for the new one
          _currentState = new list< vector<State> >;
          _currentFaults = new list< set<Event> >;

          // for each previous candidate (previousCurrentState,previousCurrentFaults), do....
          list< vector<State> >::const_iterator previousCurrentStateIt = previousCurrentState->begin();
          list< set<Event> >::const_iterator previousCurrentFaultsIt = previousCurrentFaults->begin();
          while((previousCurrentStateIt != previousCurrentState->end())
                        &&
                        (previousCurrentFaultsIt != previousCurrentFaults->end()))
                {
                  State previousState = previousCurrentStateIt->front(); // only one state in the list here

                  // futureStates are the possible futurs of previousState
                  list<  pair< State,set<Event> > > & futureStates = solutions[previousState];
                  for(list<  pair<State,set<Event> > >::const_iterator futureStateIt = futureStates.begin();
                          futureStateIt != futureStates.end(); ++futureStateIt)
                        {
                          // futureState is a possible futur of previousState
                          State futureState = futureStateIt->first;
                          // futureFaults is  set to be  the faults that occurred BEFORE previousState  and is appended
                          // to the faults that occurred between previousState and futureState 
                          set<Event> futureFaults = *previousCurrentFaultsIt;
                          for(set<Event>::const_iterator codeIt = futureStateIt->second.begin();
                                  codeIt != futureStateIt->second.end();
                                  ++codeIt)
                                {
                                  futureFaults.insert(*codeIt);
                                }
                          // check whether the couple (futureState, futureFaults) is already in the new diagnosis
                          bool found = false;   
                          list< vector<State> >::const_iterator currentStateIt = _currentState->begin();
                          list< set<Event> >::const_iterator currentFaultsIt = _currentFaults->begin();
                          while((currentStateIt != _currentState->end())
                                        &&
                                        (currentFaultsIt != _currentFaults->end())
                                        && 
                                        (!found))
                                {
                                  found = (currentStateIt->front() == futureState)
                                        && (*currentFaultsIt == futureFaults);
                                  ++currentFaultsIt;
                                  ++currentStateIt;
                                }
                          if(!found)
                                {
                                  // (futureState, futureFaults) is a new diagnosis candidate, we save it.
                                  _currentState->push_back(vector<State>());
                                  _currentGlobalStates.insert(futureState);
                                  _currentState->back().push_back(futureState);
                                  _currentFaults->push_back(futureFaults);
                                }                       
                        }
                  ++previousCurrentFaultsIt;
                  ++previousCurrentStateIt;     
                }
        
          // let us do some cleaning, c++ is not java, it does not do the job for us....
          for(list< vector<State> >::iterator it = previousCurrentState->begin();
                  it != previousCurrentState->end();
                  ++it)
                {
                  it->clear();
                }
        
          delete previousCurrentFaults;
          delete previousCurrentState;  

          ensure(Exception,!_currentGlobalStates.empty(),"_globalModelDiagnose: _currentGlobalStates is empty"); 
          ensure(Exception,thereIsSolution,"_globalModelDiagnose: cannot determine a solution (bug or check scenario)");
        
        }
          

        /********************************************************************************************/


        void FaultDiagnosis::diagnoserDiagnose(const Event & obs)
        {
          _diagnoser->diagnose(obs);
        }

        
        /********************************************************************************************/

        void FaultDiagnosis::globalModelDiagnose(const Event & obs)
        {
          // this method is in charge of diagnosing 'label'
          // with a naive search (BFS) on the global model

         

          // this structure is in charge of saving the results
          // By observing 'label' from one initial state one may reach
          // a set of states. And to reach them, it may be possible
          // that fault events occur
          unordered_map< State,  list<  pair<State,set<Event> > > > solutions;


          // the state space is (model state x faults)
          // during the search we need to know the state of the model AND
          // the set of faults that can occur before reaching this state.
          list< pair<State,set<Event> > > visitingStates;
        
          // here, i will store model states which I found out that no future
          // trajectory can emit the observation 'label'
          // a state in "noSolutions" means that the previous diagnosis is refined
          // any candidate in noSolutions is incompatible with the new observation.
          set<State> noSolutions;
          bool thereIsSolution = false;
        
          // loop on the current belief state
          for(set<State>::const_iterator stateIt = _currentGlobalStates.begin();
                  stateIt != _currentGlobalStates.end();
                  ++stateIt)
                {
                  // just to avoid visiting states an infinite number of time, one is enough
                  unordered_multimap< State , set<Event> > visitedOrVisitingStates;

                  // feel lucky, otherwise i put the current state in the queue and tag it
                  // as  visitedOrVisiting to avoid to put it again in the queue afterwards.
                  if(noSolutions.find(*stateIt) == noSolutions.end())
                        {
                          visitingStates.push_back( make_pair(*stateIt, set<Event>()) );        
                          visitedOrVisitingStates.insert(visitingStates.back());
                        }

                  // as long as the queue is not empty, there are states to visit
                  while(!visitingStates.empty())
                        {
                          // current model state
                          State & currentState = visitingStates.front().first;
                          // current set of fault that has occured before 'currentState'
                          set<Event> & currentFaults =  visitingStates.front().second;
                        
                        
                        
                          bool noSolutionForThisState = true;
                          // let's have a look at the successors of the currentState
                          for(ObservableComponent::OutputTransitionIterator outTransIt = _globalModel->outputTransitionBegin(currentState);
                                  outTransIt != _globalModel->outputTransitionEnd(currentState); ++outTransIt)
                                {
                                  if(_globalModel->getEvent(*outTransIt) == obs)
                                        { 
                                          // good, a transition is labeled with 'obs' so the target is a solution
                                          thereIsSolution = true;
                                          noSolutionForThisState = false;
                                          // so, from *stateIt, by observing 'obs', we can reach 'outTransIt->target()' and
                                          // 'currentFaults' has occurred during the trip
                                          solutions[*stateIt].push_back(make_pair(outTransIt->target(), currentFaults) );
                                        }                       
                                  else
                                        {
                                          // no luck, it is not obs :-(
 

                                          if(!_globalModel->mask().isObservable(_globalModel->getEvent(*outTransIt)))
                                                {
                                                  // seems this transition is not observable 
                                                  // so we need to explore its successors...
                                                   
                                                  if(noSolutions.find(outTransIt->target()) == noSolutions.end())
                                                        {
                                                          // the target of the transition is not registered as a "no solution state"
                                                          // so  we need to explore its successors...
                                                          noSolutionForThisState = false;
                                                          set<Event> newCurrentFaults = currentFaults;
                                                         
                                                          if(_faultEvents.find(_globalModel->getEvent(*outTransIt)) != _faultEvents.end())
                                                                {
                                                                  // the visited transitions trigger a fault, we need to keep trace of it!
                                                                  
                                                                  newCurrentFaults.insert(_globalModel->getEvent(*outTransIt));
                                                                }

                                                          //ok now we need to explore the state (outTransIt->target(), newCurrentFaults)
                                                          // but it may already be in the queue, let's have a look....
                                                          typedef unordered_multimap <State, set<Event> >::const_iterator MapIterator; 
                                                          pair< MapIterator, MapIterator > range = visitedOrVisitingStates.equal_range(outTransIt->target());
                                                          
                                                          bool found = false;
                                                          MapIterator visitedIt = range.first;
                                                          while( (!found) && (visitedIt != range.second) )
                                                                {
                                                                  found = visitedIt->second == newCurrentFaults;
                                                                  ++visitedIt;
                                                                }       
                                                          
                                                          if(!found)
                                                                {
                                                                  // the state (outTransIt->target(), newCurrentFaults) is not in the queue,
                                                                  // need to add it in the end (that is a BFS)
                                                                  visitingStates.push_back(make_pair(outTransIt->target(),newCurrentFaults));
                                                                  visitedOrVisitingStates.insert(visitingStates.back()); 
                                                                }
                                                        }
                                                }
                                        }
                                }
                          if(noSolutionForThisState)
                                {
                                  // from current state, we have not found any trajectory that
                                  // emit the observation 'obs'. Let us  save this information somewhere
                                  // as it may help for further search...
                                  noSolutions.insert(currentState); 
                                }
                          // finally current_state has been visited, let us handle the next state in the queue....
                          visitingStates.pop_front();
                        }
                }
        
          if(!thereIsSolution)
                {
                  // this is the worst case ever, it should never happen with the hypotheses we took for pj work.
                  // anyway, code is never perfect, just for debugging...
                  cout << "No solution found for the following problem" << endl;
                  cout << "Observation = " << obs.label() << endl;
                  cout << "Previous Diagnosis = " << endl;
                  Diagnosis diagnosis;
                  getDiagnosis(diagnosis);
                  cout << diagnosis << endl;
                }       
        
          // let us update the diagnosis now!
          // don't forget that the table solutions contains the result of the search
          // between the initial beliefstate and the new belief state with
          // a record of the fault event that has occurred during this search
          // now we need to 'append' this table with the previous diagnosis
          // by updating the past set of faults with the new ones....



          // will put the new belief state here
          _currentGlobalStates.clear();

          // let save the previous belief state temporally
          list< vector<State> > * previousCurrentState  = _currentState;
          list< set<Event> > * previousCurrentFaults = _currentFaults;

          // and create new structures for the new one
          _currentState = new list< vector<State> >;
          _currentFaults = new list< set<Event> >;

          // for each previous candidate (previousCurrentState,previousCurrentFaults), do....
          list< vector<State> >::const_iterator previousCurrentStateIt = previousCurrentState->begin();
          list< set<Event> >::const_iterator previousCurrentFaultsIt = previousCurrentFaults->begin();
          while((previousCurrentStateIt != previousCurrentState->end())
                        &&
                        (previousCurrentFaultsIt != previousCurrentFaults->end()))
                {
                  State previousState = previousCurrentStateIt->front(); // only one state in the list here

                  // futureStates are the possible futurs of previousState
                  list<  pair< State,set<Event> > > & futureStates = solutions[previousState];
                  for(list<  pair<State,set<Event> > >::const_iterator futureStateIt = futureStates.begin();
                          futureStateIt != futureStates.end(); ++futureStateIt)
                        {
                          // futureState is a possible futur of previousState
                          State futureState = futureStateIt->first;
                          // futureFaults is  set to be  the faults that occurred BEFORE previousState  and is appended
                          // to the faults that occurred between previousState and futureState 
                          set<Event> futureFaults = *previousCurrentFaultsIt;
                          for(set<Event>::const_iterator codeIt = futureStateIt->second.begin();
                                  codeIt != futureStateIt->second.end();
                                  ++codeIt)
                                {
                                  futureFaults.insert(*codeIt);
                                }
                          // check whether the couple (futureState, futureFaults) is already in the new diagnosis
                          bool found = false;   
                          list< vector<State> >::const_iterator currentStateIt = _currentState->begin();
                          list< set<Event> >::const_iterator currentFaultsIt = _currentFaults->begin();
                          while((currentStateIt != _currentState->end())
                                        &&
                                        (currentFaultsIt != _currentFaults->end())
                                        && 
                                        (!found))
                                {
                                  found = (currentStateIt->front() == futureState)
                                        && (*currentFaultsIt == futureFaults);
                                  ++currentFaultsIt;
                                  ++currentStateIt;
                                }
                          if(!found)
                                {
                                  // (futureState, futureFaults) is a new diagnosis candidate, we save it.
                                  _currentState->push_back(vector<State>());
                                  _currentGlobalStates.insert(futureState);
                                  _currentState->back().push_back(futureState);
                                  _currentFaults->push_back(futureFaults);
                                }                       
                        }
                  ++previousCurrentFaultsIt;
                  ++previousCurrentStateIt;     
                }
        
          // let us do some cleaning, c++ is not java, it does not do the job for us....
          for(list< vector<State> >::iterator it = previousCurrentState->begin();
                  it != previousCurrentState->end();
                  ++it)
                {
                  it->clear();
                }
        
          delete previousCurrentFaults;
          delete previousCurrentState;  

          ensure(Exception,!_currentGlobalStates.empty(),"_globalModelDiagnose: _currentGlobalStates is empty"); 
          ensure(Exception,thereIsSolution,"_globalModelDiagnose: cannot determine a solution (bug or check scenario)");
        
        }

  };
};