/* (C) Copyright 1997 Albert Ludwigs University Freiburg *     Institute of Computer Science * * All rights reserved. Use of this software is permitted for  * non-commercial research purposes, and it may be copied only  * for that use.  All copies must include this copyright message. * This software is made available AS IS, and neither the authors * nor the  Albert Ludwigs University Freiburg make any warranty * about the software or its performance.  *//* Backchain on a conjunction of literals and determine   the ground facts from the initial state that are used.      Usual circle:   fbackchain_goals()   -->    fbackchain_one_goal()                           ^                         |                           |                         v		   cond_fbackchain_ops  <--    fbackchain_ops()*/#include "ipp.h"#include "rifo.h"#include "instantiateIV.h"static void pprefix( int count ); /* global variables */static int curdepth; /* current depth of backchaining search */int backchain_on_ini = 1; /* backchain on initial facts */long nodes_visited = 0;int unionstrategy;  int mindepth = 1, maxdepth = 20;int rifo_display_info = 0;settype* empty_set; /* a kind of constant which is initialised in		     find_relevant_initial_facts() */rifo_op_array rel_op_array;rifo_fact_array rel_fct_array;  /* relevance info for facts */Integers_ptr * op_lookup_table; /* look up actions that generate 				   a given fact *//* used to save actions, initial and goal state when using metastrategy */BitOperator *save_BitOperators;   FactInfoPair *save_initial_state;FactInfoPair *save_goal_state;settype *secondary_fact_set;int opslevel;/* used to print out current search depth  */void pprefix( int count ){  register int i;  for ( i=0; i<count; i++ ) printf( " " );  printf( "(%d)--",count );}/* some functions initializing the data structures */ /* initialize rel_op_array with operator list gbit_operators */void init_op_array( void ){   BitOperator *actop;  int i, j;#ifdef MEMORY_INFO  rifo_memory += MAX_OPS * sizeof( rifo_relevant_op );#endif  /* now put all operators into array */  if ( rifo_display_info >= 3 )     printf( "> Initializing operator array with operator list...\n" );  if ( gnum_bit_operators > MAX_OPS )    { fatal_error( "Number of Operators too high, increase MAX_OPS and recompile!\n"); }    actop = gbit_operators;  i=0;  while (actop)    {      rel_op_array[i].opnode = New_BitOperator (actop->name);      rel_op_array[i].opnode->p_preconds = actop->p_preconds;      rel_op_array[i].opnode->n_preconds = actop->n_preconds;      rel_op_array[i].opnode->unconditional = actop->unconditional;      rel_op_array[i].opnode->conditionals = actop->conditionals;      for (j=0; j < actop->num_vars;j++)	rel_op_array[i].opnode->inst_table[j] = actop->inst_table[j];      rel_op_array[i].opnode->num_vars = actop->num_vars;      actop = actop->next;      i++;          }}/* initialize rel_fct_array with initial state plus constants */void init_fct_array( void ){  int elcnt, i, index;#ifdef MEMORY_INFO  rifo_memory += (2*MAX_RELEVANT_FACTS + MAX_CONSTANTS_TABLE)* sizeof( rifo_relevant_fact );#endif  if ( rifo_display_info >= 3 )     printf( "> Initializing fact array with initial state...\n" );  /* initialise memcode with default value -1     meaning: fact has not been used yet */  for (i=0; i<2*gnum_relevant_facts+gconstants_table_size; i++)    {      rel_fct_array[i].memcode = -1;    }  elcnt = 0;  /* put initial facts into array with indices 0-2*gnum_relevant_facts-1 */    for ( i = 0; i < gnum_relevant_facts; i++ )     {       if ( get_bit( gbit_initial_state->positive->vector, gft_vector_length, i ))        { /* fact is positive */          rel_fct_array[i].is_relevant = 0;	  rel_fct_array[i].is_initial = 1;	  rel_fct_array[i].memcode = elcnt++;	  if ( rifo_display_info >= 5 )	    { 	     printf( ">> ... adding %d to fact array \n", i);	    }	  /* used_facts contains one set with one member: i */	  rel_fct_array[i].used_facts = make_set_list(i);	}          else if ( get_bit( gbit_initial_state->negative->vector, gft_vector_length, i))      { /* fact is negative */	index = i + gnum_relevant_facts;	rel_fct_array[index].is_relevant = 0;	rel_fct_array[index].is_initial = 1;	rel_fct_array[index].memcode = elcnt++;	if ( rifo_display_info >= 5 ) 	  printf( ">> ... adding %d to fact array \n", index);	/* used_facts contains one set with one member: index */	rel_fct_array[index].used_facts = make_set_list(index);      }     if ( elcnt > MAXSETSIZE-1 )      fatal_error ( "Too many initial facts.\n Change MAXSETSIZE and SETARSIZE and recompile!\n" );    }  /* now add constants to rel_fct_array with indices starting with      2*gnum_relevant_facts                                     */  for (i=2*gnum_relevant_facts; 	 i<2*gnum_relevant_facts+gconstants_table_size; i++)    {      rel_fct_array[i].is_relevant = 0;      rel_fct_array[i].memcode = elcnt++;      if ( rifo_display_info >= 5 )	printf( ">> ... adding constant %d to fact array \n", i);    }}void init_lookup_table( void ){  Effect *eff;  int i, j, t;  Integers *act;  op_lookup_table = (Integers_ptr *) calloc (2*gnum_relevant_facts, sizeof(Integers_ptr ));#ifdef MEMORY_INFO  rifo_memory += gnum_relevant_facts * 2 * sizeof( Integers_ptr );#endif  for ( j = 0; j<2*gnum_relevant_facts; j++ ) op_lookup_table[j] = NULL;     for ( i=0; i<gnum_bit_operators; i++ )    { /* go through all operators */      for ( t=0; t<2; t++)	{ /* first check unconditional, then conditional effects */	  if ( t==0 )	    eff = rel_op_array[i].opnode->unconditional;	  else 	    eff = rel_op_array[i].opnode->conditionals;	  while ( eff )	    { /* if any fact is an effect, put operator number into list*/ 	      for ( j=0; j<gnum_relevant_facts; j++ )		{		  if ( get_bit( eff->p_effects->vector, gft_vector_length, j ))		    { 		      if (op_lookup_table[j] == NULL)			op_lookup_table[j] = New_integers( i );		      else 			{			  act = op_lookup_table[j];			  while (!(act->next == NULL)) 			    { act = act->next; }			  act->next = New_integers( i ); 			}		    }		 		  if ( get_bit( eff->n_effects->vector, gft_vector_length, j ))		    { 		      if (op_lookup_table[j+gnum_relevant_facts] == NULL)			op_lookup_table[j+gnum_relevant_facts] = New_integers( i );		      else 			{			  act = op_lookup_table[j+gnum_relevant_facts];			  while (act->next != NULL) 			    { act = act->next; }			  act->next = New_integers( i );			}		 		    }		}	      eff = eff->next;	    }	}    }} /* the heart of this program: the backchaining functions *//* go back in the factgeneration tree from one fact to the operators   that could possibly create it */set_list fbackchain_one_goal( int depth, int index ){  struct rifo_relevant_fact f;  set_list sl;  int nolength, j , constindex;    if (index >= 2*gnum_relevant_facts)    fatal_error ( "fbackchain_one_goal: cannot backchain on objects!\n" );  f = rel_fct_array[index] ; /* get old entry */   if ( (f.memcode >= 0) && (f.is_initial) 	&& ( (!backchain_on_ini) || (depth<=0) ) )     { /* initial fact */      if ( rifo_display_info >= 4 ) 	{	  pprefix( curdepth-depth );	  printf( ">> reached initial fact %d: ", index );	  print_set_list( f.used_facts, "" );          for ( j=0; j<MAX_ARITY; j++ )	    {	      constindex = grelevant_facts[index % gnum_relevant_facts]->arguments[j];              rel_fct_array[2*gnum_relevant_facts+constindex].is_relevant = 1; 	    }	}      sl = set_copy_list( f.used_facts );    }   else if (( f.lastdepth >= depth ) && (f.lastdepth > 0))    { /* cached fact*/      if ( rifo_display_info >= 4 ) {	pprefix( curdepth-depth );	printf( ">> fact %d already cached on level %d, current level %d: ", 		 index, f.lastdepth, depth );	print_set_list( f.used_facts, "" );      }      sl = set_copy_list( f.used_facts );    }   else     { /* not known yet, cached at deeper level, or backchain on ini */      if ( depth <= 0 ) return NULL;      if ( rifo_display_info >= 4 ) 	{	  pprefix( curdepth-depth );          if( f.memcode >= 0 )            printf( ">> backchaining on fact %d ...\n", index );          else             printf( ">> cached fact %d on level %d, try again ...\n",		       index, curdepth - f.lastdepth );	}      /* that's the point: from the goal node find all possible operators	 by backchaining and save the possibility set sl */      sl = fbackchain_ops( depth-1, index ); /* backchain to get result ... */      if ( f.memcode >= 0 ) 	set_merge_into_list( &sl, &nolength, make_set( index ),0 );      if ( rifo_display_info >= 4 ) 	{	  pprefix( curdepth-depth );          if ( index < gnum_relevant_facts)	    {               printf( ">> result for positive fact %d: ", index );	      print_set_list( sl, "" );	    }          else  	    {              printf( ">> result for negative fact %d: ", index );	      print_set_list( sl, "" );            }        }      /* make entry relevant */      rel_fct_array[index].is_relevant = 1 ;      /* free if a list was created previously */      set_free_list( rel_fct_array[index].used_facts );       rel_fct_array[index].lastdepth = depth;      rel_fct_array[index].used_facts = set_copy_list( sl );    }  return sl;}/* All objects used in an instantiated operator are relevant for   this operator   They are included into a set which is the basis for the set   of relevant initial facts */set_list check_constants( int depth, short int objects[MAX_VARS], 			  short int num_objects ){  set_list sl;  int i;  int constindex;  sl = make_set_list( NOELEMENT );  for ( i = 0; i < num_objects; i++ )     {      /* adding 2*gnum_relevant_facts, because constants are stored in        rel_fct_array after pos. and neg. facts */      constindex = 2*gnum_relevant_facts + objects[i];      rel_fct_array[constindex].is_relevant = 1;      /* include object into set */      set_insert_el( sl->item, constindex );    }  return sl;}/* backchain on each of the given goals and try to reach all (AND node).   depth is the current search depth, constants_used is NULL in the beginning   and later contains the objects used by the ground operator whose preconds   are our actual goals */set_list fbackchain_goals( int depth, FactInfoPair *goals,                            short int objects_used[MAX_VARS], short int num_objects ){  set_list sl, new_sl;  int i;  nodes_visited++;        /* first find the set including all objects used on next higher level       by the ground op we're backchaining on...   */  sl = check_constants( depth, objects_used, num_objects);   for (i=0; (i<gnum_relevant_facts) && sl; i++) {       /* backchain on first goal, then make new possibility set sl from       old sl and the new set for the first goal. This is done       as long as there are still goals to backchain and the       possibility set is not empty, which would mean there is no       possibility to reach the goals */    if (get_bit(goals->positive->vector, gft_vector_length ,i))               {       new_sl = fbackchain_one_goal( depth, i);       sl = set_multiply_lists( sl, new_sl );      }    if (get_bit(goals->negative->vector, gft_vector_length ,i))               {       new_sl = fbackchain_one_goal( depth, i + gnum_relevant_facts);       sl = set_multiply_lists( sl, new_sl );      }    }  if ( rifo_display_info >= 5 )     {      pprefix( curdepth-depth );      printf( "- result: " );      pprefix( curdepth-depth );      print_set_list( sl, "- " );      printf( "\n" );    }  return sl;}/* backchains on preconditions and effect conditions because one of   the effects in eff is needed */set_list cond_fbackchain_ops( int depth, int op_number, Effect *eff ){  BitOperator *op;  FactInfoPair *new_goals;  FactInfo *pos, *neg;  set_list setl;  op = rel_op_array[op_number].opnode;    /* backchain on preconditions AND effect conditions */  pos = merge_FactInfo( op->p_preconds, eff->p_conds );  neg = merge_FactInfo( op->n_preconds, eff->n_conds );  new_goals = New_fact_info_pair( pos, neg );  setl = fbackchain_goals( (depth-1), new_goals, op->inst_table, op->num_vars );  if ( opslevel == 2 )          { /* if operator appears first time in backchaining, select it */      if ( !rel_op_array[op_number].was_selected )	{ 	  rel_op_array[op_number].was_selected = TRUE;	}      set_free_list( rel_op_array[op_number].used_facts );      rel_op_array[op_number].used_facts = set_copy_list( setl );      rel_op_array[op_number].lastdepth = depth;    }  if ( rifo_display_info >= 4 )     {      pprefix( curdepth-depth );      printf( "==== results for " );      print_op(op);      printf( "\n" );      pprefix( curdepth-depth );      print_set_list( setl, "==== " );    }  Free_fact_info( pos );  Free_fact_info( neg );  free( new_goals );   return setl;}/* in this function we backchain on one single goal and try to reach   it with different operators (OR node) */set_list fbackchain_ops( int depth, int index ){  set_list setl = NULL, new_setl = NULL;  Effect *eff;  FactInfo *eff_vector;  int op_num;  Integers *op_indices;  nodes_visited++;    if ( rifo_display_info >= 4 )     {      pprefix( curdepth-depth );      printf( ">>> trying to find operators for fact %d ...\n", index );    }       op_indices = op_lookup_table[index];  while ( op_indices != NULL )    { /* check all operator indices in list, they can generate our fact */       /* check unconditional effects */      op_num = op_indices->index;      eff = rel_op_array[op_num].opnode->unconditional;      while ( eff )	{	  if ( index < gnum_relevant_facts )	    eff_vector = eff->p_effects;	  else eff_vector = eff->n_effects;	  /* check if goal is unconditional positive effect of op */	  if ( get_bit(eff_vector->vector, gft_vector_length, index % gnum_relevant_facts)){	    if ( rifo_display_info >= 4 ) {	      pprefix( curdepth-depth );	      printf( ">>> backchaining on effect %d of operator ",		      index);	      print_op(rel_op_array[op_num].opnode);	      printf("\n");	    }	    /* mark operator as selected */	    rel_op_array[op_num].was_selected = TRUE;	    /* now backchain on operator preconditions */	    new_setl = cond_fbackchain_ops( depth, op_num, eff );	    setl = set_merge_lists( setl, new_setl );	  }	  eff = eff->next;	}          /* check conditional effects */      eff = rel_op_array[op_num].opnode->conditionals;      while ( eff ) 	{	  if (index < gnum_relevant_facts)	    eff_vector = eff->p_effects;	  else eff_vector = eff->n_effects;	  /* check if goal is a conditional positive effect of op */	  if ( get_bit(eff_vector->vector, gft_vector_length, index % gnum_relevant_facts)){	    if ( rifo_display_info >= 4 ) {	      pprefix( curdepth-depth );	      printf( ">>> backchaining on conditional effect %d of operator ",		      index);	      print_op(rel_op_array[op_num].opnode);	      printf("\n");	    }	    /* mark operator as selected */