refine_auto.m

CheckMate is a MATLAB-based tool for modeling, simulating and investigating properties of hybrid dyn

                    end
                    temp = GLOBAL_AUTOMATON{loc}.interior_region{interior_region}.state{state};
                    temp.mapping = {};
                    for k = 1:length(refinement)
        	  			temp.polytope = refinement{k};
             			new = length(GLOBAL_NEW_AUTOMATON{loc}.interior_region{interior_region}.state)+1;		
        	  			GLOBAL_NEW_AUTOMATON{loc}.interior_region{interior_region}.state{new} = temp;   
          		    end
                    GLOBAL_RAUTO_FACE_MAP{loc}{interior_region}{state} = ...
        	        [(new-length(refinement)+1): new];

                    % put all new states in the "remap" list
        	        for k = 1:length(refinement)
        	            next = length(GLOBAL_RAUTO_REMAP_LIST)+1;
        	            GLOBAL_RAUTO_REMAP_LIST{next} = ...
        	            [loc interior_region (new-length(refinement)+k)];
        	        end
                else
                    % if current state is not to be refined, retain all the information
                    % except that children and out-of-bound flag must be fixed later.
                    temp = GLOBAL_AUTOMATON{loc}.interior_region{interior_region}.state{state};
                    new = length(GLOBAL_NEW_AUTOMATON{loc}.interior_region{interior_region}.state)+1;
                    GLOBAL_NEW_AUTOMATON{loc}.interior_region{interior_region}.state{new} = temp;
                    GLOBAL_RAUTO_FACE_MAP{loc}{interior_region}{state} = [new];
                    untouched_states=[untouched_states ; loc interior_region new];
                end
            end
        end
    end
end

% Update children for each state where each child state (which must be a
% face state) is mapped from the old index in GLOBAL_AUTOMATON to the new
% index for GLOBAL_NEW_AUTOMATON. Any child state that is split in the
% refinement is mapped accordingly into multiple children in
% GLOBAL_NEW_AUTOMATON.

for l = GLOBAL_PIHA.InitialLocation_Cells(:,1)
  for s = 1:length(GLOBAL_NEW_AUTOMATON{l}.initstate)
    
    [children, mapping]=update_children(...
       GLOBAL_NEW_AUTOMATON{l}.initstate{s}.children,l,s,0,untouched_states);
    GLOBAL_NEW_AUTOMATON{l}.initstate{s}.children=children;
    GLOBAL_NEW_AUTOMATON{l}.initstate{s}.mapping=mapping;
  end
end

for l = 1:length(GLOBAL_NEW_AUTOMATON)
    if ~isempty(GLOBAL_NEW_AUTOMATON{l})
        for f = 1:length(GLOBAL_NEW_AUTOMATON{l}.interior_region)
            for s = 1:length(GLOBAL_NEW_AUTOMATON{l}.interior_region{f}.state)
              [children,mapping] = update_children(...
                 GLOBAL_NEW_AUTOMATON{l}.interior_region{f}.state{s}.children,l,f,s,untouched_states);
                 GLOBAL_NEW_AUTOMATON{l}.interior_region{f}.state{s}.children=children;
                GLOBAL_NEW_AUTOMATON{l}.interior_region{f}.state{s}.mapping=mapping;
            end
      end
  end    
end
return

% -----------------------------------------------------------------------------

function [children_new,mapping] = update_children(children,src_loc,src_int_region,src_st,untouched_states)

global GLOBAL_RAUTO_FACE_MAP
global GLOBAL_NEW_AUTOMATON

%Update the children.  If the state was not on the 'to be refined' list,
%and the 'child' was on the 'to be refined' list, then intersect the
%mapping with the child to see if it is still a child.
have_not_been_refined_flag=ismember([src_loc src_int_region src_st],untouched_states,'rows');
mapping=[];

children_new = [];
for k = 1:size(children,1)
  loc = children(k,1);
  interior_region = children(k,2);
  state = children(k,3);
  map = GLOBAL_RAUTO_FACE_MAP{loc}{interior_region}{state};
  for l = 1:length(map)
     if have_not_been_refined_flag&~ismember(children(k,:),untouched_states,'rows')
        if src_st==0
           inters=GLOBAL_NEW_AUTOMATON{src_loc}.initstate{src_int_region}.mapping{k}&...
                 GLOBAL_NEW_AUTOMATON{loc}.interior_region{interior_region}.state{map(l)}.polytope;
           if ~isempty(inters)
              children_new = [children_new; loc interior_region map(l)];
              mapping{length(mapping)+1}=inters;
           end
        else
           inters=GLOBAL_NEW_AUTOMATON{src_loc}.interior_region{src_int_region}.state{src_st}.mapping{k}&...
                 GLOBAL_NEW_AUTOMATON{loc}.interior_region{interior_region}.state{map(l)}.polytope;
           if ~isempty(inters)
              children_new = [children_new; loc interior_region map(l)];
              mapping{length(mapping)+1}=inters;
           end
        end
      elseif have_not_been_refined_flag&ismember(children(k,:),untouched_states,'rows')
        children_new = [children_new; loc interior_region map(l)];
        mapping{length(mapping)+1} = GLOBAL_NEW_AUTOMATON{loc}.interior_region{interior_region}.state{map(l)}.polytope;
      else
        children_new = [children_new; loc interior_region map(l)];
     end   
   end
end

% -----------------------------------------------------------------------------

function [refinement,non_reachable] = refine_interior_region_state(XSYSidx,discard_flag)

global GLOBAL_PIHA
global GLOBAL_AUTOMATON
global GLOBAL_TRANSITION
global GLOBAL_REV_TRANSITION
global GLOBAL_AUTO2XSYS_MAP
global GLOBAL_XSYS2AUTO_MAP
global GLOBAL_APPROX_PARAM

%This function returns: 
%   1) 'refinement' - A vector of polytopes  of the state 
%   2) 'non_reachable' - a index vector. It contains information about which elements
%       of 'refinement' are not reachable by any of the original parents.

% Find location for the given state
tmp = GLOBAL_XSYS2AUTO_MAP{XSYSidx};
dstloc = tmp(1);

% Find parent states
parents = GLOBAL_REV_TRANSITION{XSYSidx};

% Find the polytope associated with the state to be refined
if length(tmp)==3
    if tmp == [1 1 42]
        pause
    end
end
polytope = get_auto_state('current',tmp,'polytope');

%Start refinement with the polytope associated with the state to be refined
refinement = {polytope};
potential_parents = parents;
reachable=[];

for k = 1:length(parents)
  % Find location for each parent state
  idx = GLOBAL_XSYS2AUTO_MAP{parents(k)};
  srcloc = idx(1);
  % Find the index (from the source) to the mapping that leads to the destination
  index = find_src_mapping_index(idx,tmp);
  % Get the mapping of the parent on the face found above
  mapping = get_auto_state('current',idx,['mapping{' num2str(index) '}']);
  
  overall_dynamics = check_overall_dynamics(GLOBAL_PIHA.SCSBlocks, ...
      GLOBAL_PIHA.Locations{srcloc}.q);
   
   [CE,dE,CI,dI] = linearcon_data(mapping);
   if isempty(dE)
   	mappingbox = linearcon(-CE,-dE,CI,dI);
   else
       %mappingbox = linearcon(-CE,-dE,CI,dI);
      mappingbox = grow_polytope_for_iautobuild(CE,dE,CI,dI,tmp);
   end
   
   refinement_new = refinement;
   
    for l = 1:length(refinement)
    % Split the lth patch in the refinement into the part that is not in
    % mapping box and the part that overlaps with the mapping box.
    overlap = refinement{l} & mappingbox;
    reachflag=ismember(l,reachable);
    if ~isempty(overlap)
      %new = length(refinement_new)+1;
      refinement_new{l} = overlap;
      if ~reachflag
         reachable=[reachable l];
      end
      
    
    diff = refinement{l} - mappingbox;
    if ~isempty(diff)
	for m = 1:length(diff)
	  new = length(refinement_new)+1;
     refinement_new{new} = diff{m};
     if reachflag==1
        reachable=[reachable new];
     end
     
	end
      else
	fprintf(1,'dropped %d polytopes\n',length(diff))
      end
   end
   end
  refinement = refinement_new;
end

if length(refinement) == 1
  % if no refinement has been made, bisection the polytope
  [con1,con2] = split_polytope(polytope,GLOBAL_APPROX_PARAM.W);
  refinement = {con1 con2};
  reachable=[1 2];
end

non_reachable=setdiff([1:length(refinement)],reachable);

return

% -----------------------------------------------------------------------------

function index = find_src_mapping_index(src,dst)

global GLOBAL_AUTOMATON

if length(src)==3
	[dum1,dum2,index]=intersect(dst,GLOBAL_AUTOMATON{src(1)}.interior_region{src(2)}.state{src(3)}.children,'rows');
else
	[dum1,dum2,index]=intersect(dst,GLOBAL_AUTOMATON{src(1)}.initstate{src(2)}.children,'rows');   
end


if isempty(index)
  fprintf(1,['refine_auto.m: Impossible destination location ' ... 
	'indicated in the given state index.'])
  index = 0;
  return
end
return