/********************************************************************* * File: instantiateIV.c * * Description: routines that perform the final instantiation  * *                        - collect relevant facts and adjust ATOMs to them * *                        - create BitMap representation of domain * * Author: Joerg Hoffmann 1999 * *********************************************************************/ /********************************************************************* * (C) Copyright 1998 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.  *********************************************************************//********************************************************************* * * one thing that I'd like to say about the instantiation code is this: * *      it might look terrible to have four big files of C code just *      to instantiate the operators, and in fact, it is. * *      on the other hand, this is only the result of the terrible *      things that the domain designer is allowed to define in  *      full scale PDDL. * *      though the code produces a very tight domain representation *      in all cases, see Technical Report 122  *      "Handling of Inertia in a Planning System" on the IPP homepage, *      there are quite some cases where it could be made far more *      efficient. At the very least, if one is facing a simple STRIPS *      domain, it's better to skip the whole thing and use a specialised *      algorithm which will be faster than this code by factors in the order *      of hundreds... * **********************************************************************/#include "ipp.h"#include "output.h"#include "utilities.h"#include "memory.h"#include "pddl.h"#include "instantiateI.h"#include "instantiateII.h"#include "instantiateIII.h"#include "instantiateIV.h" /* ------------------------------ COLLECT RELEVANT FACTS ----------------- *//* a bit INEFFICIENT: all but lindex are 1/0 decisions, so it would be sufficient * to use BitVectors here. Not a big deal, though, I guess, as memory is freed * afterwards anyway. */int_pointer lpos[MAX_PREDICATES_TABLE];int_pointer lneg[MAX_PREDICATES_TABLE];int_pointer luse[MAX_PREDICATES_TABLE];int_pointer lindex[MAX_PREDICATES_TABLE];void collect_relevant_facts( void ){  int i, j, size;  CodeOperator *oo;  CodeNode *n;  for ( i=0; i<gpredicates_table_size; i++ ) {    size = 1;    for ( j=0; j<garity[i]; j++ ) {      size *= gconstants_table_size;    }    lpos[i] = ( int_pointer ) calloc( size, sizeof( int ) );    lneg[i] = ( int_pointer ) calloc( size, sizeof( int ) );    luse[i] = ( int_pointer ) calloc( size, sizeof( int ) );    lindex[i] = ( int_pointer ) calloc( size, sizeof( int ) );    for ( j=0; j<size; j++ ) {      lpos[i][j] = 0;      lneg[i][j] = 0;      luse[i][j] = 0;      lindex[i][j] = -1;    }  }  if ( gcode_initial_state ) {    for ( n = gcode_initial_state->sons; n; n=n->next ) {      lpos[n->predicate][pos_neg_use_index_adress( n->predicate, n->arguments )] = 1;    }  }  for ( oo = ginst_code_operators; oo; oo=oo->next ) {    if ( oo->conditionals ) {      /* ops come from multiplying without clean up, so effects can be       * empty here       */      for ( n = oo->conditionals->sons; n; n = n->next ) {	make_pos_neg_use_index_entries( n->sons->next );      }    }  }  /* now the relevant atoms are exactly those which   * have a one at their adress in both lpos[] and lneg[] table.   * these atoms have their fact index set in the lindex[]   * table (at the appropriate adress), and, for debugging   * reasons, their predicate and arguments are stored    * at their index in grelevant_facts[] table.   */  if ( gcmd_line.display_info == 7 ) {    printf("\nselected the following facts as relevant:\n");    for ( i=0; i<gnum_relevant_facts; i++ ) {      printf("\n%d: ", i);      print_fact( grelevant_facts[i]->predicate, grelevant_facts[i]->arguments );    }    printf("\ntotal number of relevant facts: %d\n\n", gnum_relevant_facts);  }  set_relevants_in_condition( &gcode_initial_state );  simplify_condition_CodeNode( &gcode_initial_state, FALSE, FALSE );  set_relevants_in_condition( &gcode_goal_state );  detect_tautologies_in_condition_CodeNode( &gcode_goal_state, FALSE );  simplify_condition_CodeNode( &gcode_goal_state, FALSE, TRUE );  if ( !gcode_goal_state ||       gcode_goal_state->connective == TRU ) {    times( &gend );    gtotal_time += ( float ) ( ( gend.tms_utime - gstart.tms_utime 				 + gend.tms_stime - gstart.tms_stime ) / 100.0 );    printf("\n\n\nipp: goal can be simplified to TRUE. no plan needed\n");    printf("\nelapsed time: %7.2f seconds\n\n", gtotal_time);    exit( 1 );  }  if ( gcode_goal_state->connective == FAL ) {    times( &gend );    gtotal_time += ( float ) ( ( gend.tms_utime - gstart.tms_utime 				 + gend.tms_stime - gstart.tms_stime ) / 100.0 );    printf("\n\n\nipp: goal can be simplified to FALSE. no plan will solve it\n");    printf("\nelapsed time: %7.2f seconds\n\n", gtotal_time);    exit( 1 );  }   for ( oo = ginst_code_operators; oo; oo=oo->next ) {    set_relevants_in_condition( &(oo->preconds) );    if ( oo->conditionals ) {      for ( n = oo->conditionals->sons; n; n = n->next ) {	set_relevants_in_condition( &(n->sons) );	set_relevants_in_effect( &(n->sons->next) );      }    }  }  for ( i=0; i<gpredicates_table_size; i++ ) {    free ( lpos[i] );    free ( lneg[i] );    free ( luse[i] );    free ( lindex[i] );  }  gft_vector_length = ( ( int ) gnum_relevant_facts / gcword_size );  if ( ( gnum_relevant_facts % gcword_size ) > 0 ) gft_vector_length++;}void set_relevants_in_condition( CodeNode **n ){  int adr;  CodeNode *i;  if ( !(*n) ) {    return;  }  if ( (*n)->connective == ATOM ) {    if ( (*n)->predicate == -1 ) {      printf("\neq predicate in fully instantiated formula! ERROR\n\n");      exit( 1 );    }    adr = pos_neg_use_index_adress( (*n)->predicate, (*n)->arguments );    if ( !lpos[(*n)->predicate][adr] ) {      if ( gcmd_line.display_info == 102 ) {	printf("\ndetected irrelevant (only negative) fact: ");	print_fact( (*n)->predicate, (*n)->arguments );      }      (*n)->connective = FAL;      free_CodeNode( (*n)->sons );      (*n)->sons = NULL;      return;    }    if ( !lneg[(*n)->predicate][adr] ) {      if ( gcmd_line.display_info == 102 ) {	printf("\ndetected irrelevant (only positive) fact: ");	print_fact( (*n)->predicate, (*n)->arguments );      }      (*n)->connective = TRU;      free_CodeNode( (*n)->sons );      (*n)->sons = NULL;      return;    }    /* fact is relevant;     * store it's index, for simplicity into (*n)->var:     * at this point, we don't need this int anymore     */    (*n)->var = lindex[(*n)->predicate][adr];    return;  }  if ( (*n)->connective == NOT ) {    set_relevants_in_condition( &((*n)->sons) );    return;  }  if ( (*n)->connective == AND ||       (*n)->connective == OR ) {    for ( i = (*n)->sons; i; i=i->next ) {      set_relevants_in_condition( &i );    }    return;  }  if ( (*n)->connective != TRU &&       (*n)->connective != FAL ) {    printf("\nrelevants shouldn't get here: non ATOM,NOT,AND,OR,TRU,FAL %d in condition\n\n",	   (*n)->connective);    exit( 1 );  }}void set_relevants_in_effect( CodeNode **n ){  CodeNode *i;  int adr;  for ( i = (*n)->sons; i; i = i->next ) {    if ( i->connective == NOT ) {      adr = pos_neg_use_index_adress( i->sons->predicate, i->sons->arguments );      if ( !luse[i->sons->predicate][adr] ) {	i->sons->var = -1;	continue;      }      i->sons->var = lindex[i->sons->predicate][adr];      continue;    }    adr = pos_neg_use_index_adress( i->predicate, i->arguments );    i->var = lindex[i->predicate][adr];  }}int pos_neg_use_index_adress( int predicate, ArgArray arguments ){  int r = 0, b = 1, i;  for ( i=garity[predicate]-1; i>-1; i-- ) {    r += b * arguments[i];    b *= gconstants_table_size;    /* NOTE: we could use less space here by relying on the type     *       defined for argument i of predicate      */  }  return r;}void make_pos_neg_use_index_entries( CodeNode *n ){  int adr;  CodeNode *nn;  RelevantFact *tmp;  for ( nn = n->sons; nn; nn=nn->next ) {        if ( nn->connective == NOT ) {      adr = pos_neg_use_index_adress( nn->sons->predicate, nn->sons->arguments );      lneg[nn->sons->predicate][adr] = 1;      if ( lpos[nn->sons->predicate][adr] &&	   !luse[nn->sons->predicate][adr] ) {	if ( gnum_relevant_facts == MAX_RELEVANT_FACTS ) {	  printf("\nincrease MAX_RELEVANT_FACTS! (current value: %d)\n\n",		 MAX_RELEVANT_FACTS);	  exit( 1 );	}	/* new relevant predicate!	 *	 * here, we can have pos[] several times. to make sure each fact	 * is made relevant only once, we need use - information.	 *	 * NOTE: the facts that get here are exactly the initials that can be	 *       deleted	 */	luse[nn->sons->predicate][adr] = 1;	lindex[nn->sons->predicate][adr] = gnum_relevant_facts;	tmp = new_RelevantFact( nn->sons );	grelevant_facts[gnum_relevant_facts++] = tmp;      }    } else {      adr = pos_neg_use_index_adress( nn->predicate, nn->arguments );      if ( !lpos[nn->predicate][adr] ) {	if ( gnum_relevant_facts == MAX_RELEVANT_FACTS ) {	  printf("\nincrease MAX_RELEVANT_FACTS! (current value: %d)\n\n",		 MAX_RELEVANT_FACTS);	  exit( 1 );	}	/* new added fact, not in initial --> relevant!	 *	 * as relevant facts all have pos[] set, we can have this only	 * once per fact.	 */	lpos[nn->predicate][adr] = 1;	lneg[nn->predicate][adr] = 1;	luse[nn->predicate][adr] = 1;	lindex[nn->predicate][adr] = gnum_relevant_facts;	tmp = new_RelevantFact( nn );	grelevant_facts[gnum_relevant_facts++] = tmp;      }    }  }}/* ---------------------  GENERATE BITMAP REPRESENTATION   ----------------- */void generate_bitmap_representation( void ){  CodeOperator *i, *j;  generate_ini_goal_bitmap_representation();  i = ginst_code_operators;  while ( i ) {    generate_BitOperators( i );    j = i;    i = i->next;