rifobackchain.c

intel ipp4.1性能库的一些例子。

	    rel_op_array[op_num].was_selected = TRUE;
	    /* Now we have to backchain on the effect conditions and on
	       the preconditions */
	    new_setl = cond_fbackchain_ops( depth, op_num, eff );
	    setl = set_merge_lists( setl, new_setl );
	  }
	  eff = eff->next;
	}
      op_indices = op_indices->next;
    }


  if ( rifo_display_info >= 4 ) 
    {
      pprefix( curdepth-depth );
      printf( ">>> results for ops to get");
      if ( index <= gnum_relevant_facts ) {printf( " positive " );}
      else if ( index <= 2*gnum_relevant_facts ) {printf( " negative " ) ;}
      printf ( "goal no. %d ...\n", index );
      pprefix( curdepth-depth );
      print_set_list( setl, "!!! " );
    }
  return setl;
}




/* functions for selecting relevant objects, facts and operators */ 


/* Marks all elements of in_set as relevant in the table of relevant facts.
   It is called at the end of the filtering process in 
   find_relevant_initial_facts() to add facts (stored in secondary_fact_set 
   by find_useful_ground_ops() that are needed for effect conditions and 
   could have been filtered out before.  */

void add_rel_objects ( settype * in_set )
{
  int start, i;
  
  start = 2*gnum_relevant_facts;
  if ( !set_empty(in_set))
    { 
      if (rifo_display_info >= 3)
	{ printf( " Object(s) " ); }
    
      for ( i=start ; i < start+gconstants_table_size; i++)
	{
	  if ( set_member(i, in_set) )
	    {
	      rel_fct_array[i].is_relevant = 1; 
	      if (rifo_display_info >=3)
		{ printf( "%s, ", gconstants_table[i-start] ); } 
	    }
	  else rel_fct_array[i].is_relevant = 0;
	}
      if (rifo_display_info >= 3)
	{ printf(" added.\n"); }
    }
  else
    {
      if (rifo_display_info >=3)
	{printf( " none added\n");}
    }

}

void add_rel_facts ( settype *in_set )
{
  int i, j, arity;

  if ( !set_empty(in_set))
    {
      if (rifo_display_info >= 3)
	{ printf( " Fact(s)" ); }
      for ( i=0; i<2*gnum_relevant_facts; i++)
	{  
	  if ( set_member(i, in_set) )
	    {
	      if (!rel_fct_array[i].is_relevant)
		{ rel_fct_array[i].is_relevant = TRUE; }
	      if (rifo_display_info >=3)
		{ 
		  printf( " %s", gpredicates_table[grelevant_facts[i%gnum_relevant_facts]->predicate] );
		  arity = garity[grelevant_facts[i%gnum_relevant_facts]->predicate];
		  for ( j=0; j<arity; j++ )
		   printf( " %s", gconstants_table[grelevant_facts[i%gnum_relevant_facts]->arguments[j]] );
		  printf( ", ");
		}
	    }
	}
      if (rifo_display_info >= 3)
	{ printf( " added.\n" ); } 
    }
  else
    {
      if (rifo_display_info >=3)
	{printf( " none added\n");}
    }
  if (rifo_display_info >=1)
    {printf( "\n" );}
}
 

/* build a set of initial facts appearing in a given effect list */
settype* rec_get_facts_from_eff_conds( Effect *eff )
{
  settype* s;
  int i;
  
  if ( !eff ) 
    {
      return make_set( NOELEMENT );
    }
  s = rec_get_facts_from_eff_conds( eff->next );


  for (i=0; i<gnum_relevant_facts; i++)
    { 
      if ( get_bit(eff->p_conds->vector, gft_vector_length, i))
	/* adding positive condition to set */
	{
	  if (rel_fct_array[i].memcode != -1)
	    { 
	      s = set_insert_el(s, i);
	    }
	}
      else if ( get_bit(eff->n_conds->vector, gft_vector_length, i))
	/* adding negative condition to set */
	{
	  if (rel_fct_array[i+gnum_relevant_facts].memcode != -1)
	    {
	      s= set_insert_el(s, i+gnum_relevant_facts);
	    }
	}
    }
  return s;
}
    


/* takes all operators which were used in the fact generation tree (they
   are saved in rel_op_array) but only if they use objects selected as
   relevant 
   This is the sharpest heuristic because only a few of all possible
   operators are selected */
BitOperator* find_useful_ground_ops( settype *inifactset, int* newcountp )
{
  BitOperator *act, *newop, *dummy;
  int is_ok = 0;
  set_list fact_set;
  settype* needed_facts_set = NULL;
  int num_rel_ops = 0;
  int  i;

  *newcountp = 0;  
  act = dummy = New_BitOperator( "dummy" );

  for ( i = 0; i<gnum_bit_operators; i++ ) 
    { /* check if operator was selected during backchaining */
      is_ok=0;
      if (rel_op_array[i].was_selected)
	{ /* check if all facts used by operator are relevant */ 
	  fact_set = rel_op_array[i].used_facts;
          if ( rifo_display_info >= 3 )
	    { 
	      print_op(rel_op_array[i].opnode);
	      printf( " found in tree \n" );
	    }
	  while (fact_set)
	    {
	      /* if one of the sets is a subset it might be possible */
	      if ( set_subseteq( fact_set->item, inifactset ) ) 
		{
		  is_ok = TRUE;
		  break;
		}
	      fact_set = fact_set->next;
	    }
	}
      else
	{
	  if (rifo_display_info>= 3 )
	    {
	      print_op( rel_op_array[i].opnode );
	      printf( " not found in tree \n" );
	    }
	}
      if (is_ok) 
	{ /* op can be generated from possibility set, add it*/
	  (*newcountp)++;
	  num_rel_ops++;
	  newop = act->next = rel_op_array[i].opnode;
	  
	  /* now declare all initial facts appearing as effect conditions 
	     of this operator as relevant (saved in secondary_fact_set).
	     Later they will be put into secondary_initial_facts and merged 
	     with the primarily needed ones */
	  
	  needed_facts_set = rec_get_facts_from_eff_conds( newop->unconditional );
	  secondary_fact_set = set_union( secondary_fact_set, 
					  secondary_fact_set, 
					  needed_facts_set, 1 );
	  FREE( sizeof(settype), needed_facts_set);
	  needed_facts_set = rec_get_facts_from_eff_conds( newop->unconditional );
	  secondary_fact_set = set_union( secondary_fact_set, 
					  secondary_fact_set, 
					  needed_facts_set, 1 );
          FREE( sizeof(settype), needed_facts_set);
	  act = newop;
	  if ( rifo_display_info >= 3 ) 
	    {
	      printf( " - selected operator ");
	      if ( rifo_display_info >= 5 )
		print_set_list( rel_op_array[i].used_facts, " used facts" );
	      else if ( rifo_display_info > 0 ) 
		printf( "\n");
	    }
	} 
      else 
	{ /* operator can磘 be generated from possibility set, ignore it*/
	  Free_BitOperator( rel_op_array[i].opnode );
	  if ( rifo_display_info >= 3 )
	    {
	      printf( " - ignored operator ");
	      if ( rifo_display_info >= 4 )
		print_set_list( rel_op_array[i].used_facts, " used facts" );
	      else if ( rifo_display_info > 0 ) 
		printf( "\n");
	    }
	}
    }
  act = dummy->next;
  dummy->next = NULL;
  FREE( sizeof(BitOperator), dummy);
  return act;
  
}



/* help function for filter_possible_ground_ops
   returns list of operators that use only relevant objects */
BitOperator *rec_find_possible_ground_ops( BitOperator *current_old, 
					    int * newcountp )
{
  int obj_index, i, j;
  BitOperator *act;
  settype* needed_facts_set = NULL;

  if ( !current_old ) return NULL;
  for (i=0; i < current_old->num_vars; i++)
    {
      /* calculate index for finding object in rel_fct_array*/ 
      obj_index = current_old->inst_table[i] + 2*gnum_relevant_facts;
      if ( !rel_fct_array[obj_index].is_relevant )
 
	{
	  if ( rifo_display_info >= 3 )
	    { 
	      print_op( current_old );
	      printf( " ignored, uses irrelevant object %s \n"
		      ,gconstants_table[current_old->inst_table[i]] );
	    }	
	  return rec_find_possible_ground_ops( current_old->next, newcountp );
	}
    } 

  (*newcountp)++;
  act = New_BitOperator(current_old->name);
  for ( j = 0; j < MAX_VARS; j++ ) 
    act->inst_table[j] = current_old->inst_table[j];
  act->num_vars = current_old->num_vars;
  act->p_preconds = current_old->p_preconds;
  act->n_preconds = current_old->n_preconds;
  act->unconditional = current_old->unconditional;
  act->conditionals = current_old->conditionals;  
  /* now declare all initial facts appearing as effect conditions of this
     operator as relevant (saved in secondary_fact_set). Later they will 
     be put into secondary_initial_facts and merged with the primarily 
     needed ones */
  needed_facts_set = rec_get_facts_from_eff_conds( act->conditionals );
  secondary_fact_set = set_union( secondary_fact_set, secondary_fact_set, 
				  needed_facts_set, 1 );
  act->next = rec_find_possible_ground_ops( current_old->next, newcountp );
  if ( rifo_display_info >= 3 )
    { 
      printf(" ");
      print_op( current_old );
      printf( " was selected. \n");
    }
  return act;
}





    
/*************************************************************************** 
 * main routine: find relevant facts by backchaining and minimizing the
 *  set of used initial facts and actions
 ***************************************************************************/

void find_relevant_initial_facts()
{
  set_list results = NULL;
  set_list temp;
  settype *factset = NULL;  /* union over the sets in the final pos. set */

  int numres = -1;
  int oldfnum, newfnum, newobjnum;
  int oldopnum, newopnum;
  int depth;
  int i;

  
  init_fct_array();  /* initialize fact array with inital state */
  init_op_array();   /* put operator list gbit_operators into rel_op_array */
  init_lookup_table();/* create table of operators that create specific facts */

  if ( gcmd_line.display_info )
    rifo_display_info = 1;

  /* use metastrategy if selected */
  if (rifo_meta == 2)
    {
      opslevel = 2;
      unionstrategy = 1;
    }
  else if (rifo_meta == 1)
    {
      opslevel = 1;
      unionstrategy = 1;
    }
  else
    { /* no metastrategy, use command line arguments */
      if (gcmd_line.rifo_filter > 2)
	{
	  printf( "\nrifo: unknown filtering option\n" );
	  exit( 1 );
	}
      if (gcmd_line.rifo_union > 4)
	{
	  printf( "\nrifo: unknown unionstrategy\n" );
	  exit( 1 );
	}
      switch (gcmd_line.rifo_filter) 
	{
	case 0: 
	  opslevel = 0;
	  break;
	case 1:
	  opslevel = 1;
	  break;
	case 2:
	  opslevel = 2;
	  break;
	default:
	  opslevel = 1;
	}
      switch (gcmd_line.rifo_union)
	{
	case 1:
	  unionstrategy = 0;
	  break;
	case 2:
	  unionstrategy = -10000;
	  break;
	case 3:
	  unionstrategy = -1;
	  break;
	case 4:
	  unionstrategy = 1;
	  break;
	default:
	  unionstrategy = -1;
	}
    }

  depth = mindepth;
  maxdepth = MAX(depth, maxdepth);
 
  if ( rifo_display_info >= 1 )
    {
      printf( "backchaining process started... \n" );
      printf( " using opslevel %d\n", opslevel);
    }
  if (rifo_display_info >=3)
    {
      printf( "goal state is:");
      print_Fact_Info( gbit_goal_state );
      printf( "trying to reach initial state:");
      print_Fact_Info( gbit_initial_state );
    }
  while ( depth <= maxdepth ) 
    {
      if ( rifo_display_info >= 2 )
	{
	  printf( "... using depth %d\n", depth );
	}
      /* start backchaining process on goals */
      results = fbackchain_goals( (curdepth=depth*2), gbit_goal_state, NULL, 0 );
      numres = set_list_length( results );
      if ( rifo_display_info >= 4 )
	printf( "... %d resulting initial-fact set%s found\n",
		numres, ( ( numres != 1 ) ? "s" : "" ) );
      if ( rifo_display_info >= 4 ) 
	{
	  temp = results;
	  while ( temp ) 
	    {
	      printf( "Initial-fact set:" );
	      print_one_set( temp->item, "", 0 );
	      printf( "\n" );
	      temp = temp->next;
	    }
	}      
      if ( numres > 0 ) 
	{ /* now build the union with one of the strategies described in
	     the paper over the sets in "results" */
	  factset = set_union_list( results, unionstrategy );
	  break;
	}
      depth++;
    }

  if ( factset == NULL ) 
    {
      printf( "Cannot find a solution for depth %d.\n",maxdepth );
      printf( "Returning original fact file.\n" );
    } 
  else 
    { /* found non-empty factset  */
      oldfnum = gnum_relevant_facts;
      oldopnum = gnum_bit_operators;
      empty_set = make_set( NOELEMENT );
      secondary_fact_set = make_set( NOELEMENT );
 
      /* use only facts mentioned in factset */
      if ( rifo_display_info >= 2 ) 
	printf( "\n filtering relevant objects...\n" ); 
      add_rel_objects( factset );
      if ( rifo_display_info >= 2 ) 
	printf( "\n filtering relevant initial facts...\n" ); 
      add_rel_facts( factset ); 
	
      if ( opslevel == 1) 
	{ /* weak filtering: only ops using relevant objects */
	  if ( rifo_display_info >= 2 ) 
	    {
	      printf( "\n filtering ground ops using relevant objects...\n" );
	    }	  
	  newopnum = 0;
	  gbit_operators = rec_find_possible_ground_ops( gbit_operators, &newopnum );
	  if ( rifo_display_info >= 1 ) 
	    {
	      printf( " rifo: %d out of %d operators selected.\n", 
		      newopnum, oldopnum );
	    }
	}
      if ( opslevel == 2 ) 
	{/* strong filtering: only operators appearing in fact generation tree */
	  if ( rifo_display_info >= 2 ) 
	    {
	      printf( "\n filtering ground ops appearing in the fact generation tree...\n" ); 
	    }
	  newopnum = 0;
	  gbit_operators = find_useful_ground_ops( factset, &newopnum );
	  if ( rifo_display_info >= 1 ) 
	    {
	      printf( " rifo: %d out of %d ground operators selected.\n", 
		      newopnum, oldopnum );
	    }
	}
      /* after having selected the ground ops some initial facts 
	 appearing as effect conditions have to be added */
      if ( rifo_display_info >= 2 ) 
	printf( "\n adding initial facts needed as effect conditions..." ); 
      add_rel_facts( secondary_fact_set ); 
      FREE( sizeof(settype), secondary_fact_set );
      
      /* count new number of relevant facts */
      newfnum = 0;
      newobjnum = 0;
      for (i=0; i<gnum_relevant_facts; i++)
	{
	  if ((rel_fct_array[i].is_relevant && rel_fct_array[i].is_initial) 
	      || (rel_fct_array[i+gnum_relevant_facts].is_relevant
		 && rel_fct_array[i+gnum_relevant_facts].is_initial))
	    { newfnum++; }
    	}
      for (i = 0 ; i < gconstants_table_size; i++ )
        {
	  if (rel_fct_array[i+ 2*gnum_relevant_facts].is_relevant)
	    { newobjnum++; }
	}
     newopnum = op_list_length( gbit_operators );
      
      if ( rifo_display_info >= 1 ) 
	{   
	  printf( " rifo: %d out of %d initial facts considered as relevant.\n", 
		  newfnum, oldfnum );
          printf( "       %d out of %d objects selected.\n\n",
		  newobjnum, gconstants_table_size );
	}
    }

  Free_lookup_table();
  set_free_list( results );
  FREE( sizeof(settype), factset);
}