instantiateii.c

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

/*********************************************************************
 * File: instantiateII.c
 *
 * Description:
 *
 * code for handling transformations on CodeNodes that can occur
 * during (almost) all stages of instantiation:
 *
 *                        - detect tautologies in PLI conditions
 *
 *                        - simplify a PLI condition
 *                        - detect trivial or inconsistent or
 *                          never applicable effects
 *                        - simplify an effect list according to that
 *                        - detect unused variables, remove them
 *                        - clean up operators
 *                       
 *
 * 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 "instantiateI.h"
#include "instantiateII.h"











/*
 *  ----------------------- DETECT TAUTOLOGIES, LIKE A \WEDGE \NEG A ETC. ... ------------
 */












void detect_all_tautologies( Bool warnings )

{

  CodeOperator *i;
  CodeNode *n, *nn;

  if ( gcmd_line.display_info == 0 ) {
    warnings = FALSE;
  }

  detect_tautologies_in_condition_CodeNode( &gcode_initial_state, warnings );
  detect_tautologies_in_condition_CodeNode( &gcode_goal_state, warnings );

  for ( i = gcode_operators; i; i = i->next ) {
    detect_tautologies_in_condition_CodeNode( &(i->preconds), warnings );
    if ( i->conditionals ) {
      for ( n = i->conditionals->sons; n; n = n->next ) {
	for ( nn = n; nn && nn->connective != WHEN; nn = nn->sons );
	detect_tautologies_in_condition_CodeNode( &(nn->sons), warnings );
	detect_tautologies_in_condition_CodeNode( &(nn->sons->next), warnings );
      }
    }
  }

}



void detect_inst_CodeOperator_tautologies( void )

{

  CodeOperator *i;
  CodeNode *n, *nn;

  for ( i = gcode_operators; i; i = i->next ) {
    detect_tautologies_in_condition_CodeNode( &(i->preconds), FALSE );
    if ( i->conditionals ) {
      for ( n = i->conditionals->sons; n; n = n->next ) {
	for ( nn = n; nn && nn->connective != WHEN; nn = nn->sons );
	detect_tautologies_in_condition_CodeNode( &(nn->sons), FALSE );
	detect_tautologies_in_condition_CodeNode( &(nn->sons->next), FALSE);
      }
    }
  }

}



void detect_tautologies_in_condition_CodeNode( CodeNode **n, Bool warnings )

{

  CodeNode *i, *j, *prev;

  if ( !(*n) ) {
    return;
  }

  if ( (*n)->connective == NOT ||
       (*n)->connective == ALL ||
       (*n)->connective == EX ) {
    detect_tautologies_in_condition_CodeNode( &(*n)->sons, warnings );
  }

  if ( (*n)->connective == AND ||
       (*n)->connective == OR ) {
    for ( i = (*n)->sons; i; i = i->next ) {
      detect_tautologies_in_condition_CodeNode( &i, warnings );
    }
    for ( i = (*n)->sons; i && i->next; i = i->next ) {
      j = i->next;
      prev = i;
      while ( j ) {
	if ( are_identical_CodeNodes( i, j ) ) {
	  if ( warnings ) {
	    printf("\nwarning: detected identical trees in con/dis junction");
	  }
	  prev->next = j->next;
	  free_CodeNode( j->sons );
	  free( j );
	  j = prev->next;
	  continue;
	}
	if ( i->connective == NOT &&
	     are_identical_CodeNodes( i->sons, j ) ) {
	  if ( warnings ) {
	    printf("\nwarning: detected A, neg A tautology");
	  }
	  (*n)->connective = ((*n)->connective == AND) ? FAL : TRU;
	  free_CodeNode( (*n)->sons );
	  (*n)->sons = NULL;
	  return;
	}
	if ( j->connective == NOT &&
	     are_identical_CodeNodes( i, j->sons ) ) {
	  if ( warnings ) {
	    printf("\nwarning: detected A, neg A tautology");
	  }
	  (*n)->connective = ((*n)->connective == AND) ? FAL : TRU;
	  free_CodeNode( (*n)->sons );
	  (*n)->sons = NULL;
	  return;
	}
	prev = j;
	j = j->next;
      }
    }
  }

  if ( (*n)->connective == ATOM &&
       (*n)->predicate == -1 &&
       (*n)->arguments[0] == (*n)->arguments[1] ) {
    if ( warnings ) {
      printf("\nwarning: detected EQ predicate with identical arguments");
    }
    (*n)->connective = TRU;
  }

  if ( (*n)->connective == ATOM &&
       (*n)->predicate == -1 &&
       (*n)->arguments[0] > -1 &&
       (*n)->arguments[1] > -1 &&
       (*n)->arguments[0] != (*n)->arguments[1] ) {
    if ( warnings ) {
      printf("\nwarning: detected EQ predicate on different objects!");
    }
    (*n)->connective = FAL;
  }

}



Bool are_identical_CodeNodes( CodeNode *n1, CodeNode *n2 )

{

  int i;
  CodeNode *c, *d;

  if ( !n1 && !n2 ) {
    return TRUE;
  }
  if ( !n1 || !n2 ) {
    return FALSE;
  }

  if ( n1->connective != n2->connective ) {
    return FALSE;
  }

  if ( n1->connective == AND ||
       n1->connective == OR ) {
    d = n2->sons;
    for ( c = n1->sons; c; c = c->next ) { 
      if ( !are_identical_CodeNodes( c, d ) ) {
	return FALSE;
      }
      d = d->next;
    }
    if ( d ) {
      return FALSE;
    }      
  } else {
    if ( n1->connective == ALL ||
	 n1->connective == EX ) {
      if ( n1->var_type != n2->var_type ) {
	return FALSE;
      }
    }
    if ( !are_identical_CodeNodes( n1->sons, n2->sons ) ) {
      return FALSE;
    }
  }
  
  if ( n1->connective == ATOM ) {
    if ( n1->predicate != n2->predicate ) {
      return FALSE;
    }
    for ( i=0; i<garity[n1->predicate]; i++ ) {
      if ( n1->arguments[i] != n2->arguments[i] ) {
	return FALSE;
      }
    }
  }

  return TRUE;

}














/*
 *  ----------------------- LOGICAL SIMPLIFICATIONS ON ALL NODE STRUCTURES ---------------
 */















void simplify_all_CodeNodes( Bool warnings )

{

  if ( gcmd_line.display_info == 0 ) {
    warnings = FALSE;
  }

  simplify_condition_CodeNode( &gcode_initial_state, warnings, FALSE );

  simplify_condition_CodeNode( &gcode_goal_state, warnings, TRUE );
  remove_unused_vars_under_CodeNode( &gcode_goal_state, warnings );
  rename_vars_under_CodeNode( &gcode_goal_state, 0 );
  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 );
  }


  simplify_all_CodeOperators( warnings );

}



void simplify_all_CodeOperators( Bool warnings )

{

  CodeOperator *i, *j, *prev;
  CodeNode *n, *nn;
  int l, k;

  for ( i = gcode_operators; i; i = i->next ) {
    simplify_condition_CodeNode( &(i->preconds), warnings, TRUE );
    if ( i->conditionals ) {
      for ( n = i->conditionals->sons; n; n = n->next ) {
	for ( nn = n; nn->connective != WHEN; nn = nn->sons );
	simplify_condition_CodeNode( &(nn->sons), warnings, TRUE );
	simplify_condition_CodeNode( &(nn->sons->next), warnings, FALSE );
      }
      clean_up_effects( &(i->conditionals), warnings );
    }

    l = 0;
    while ( l < i->num_vars ) {
      if ( !var_used_under_CodeNode( l, i->preconds ) &&
	   !var_used_under_CodeNode( l, i->conditionals ) ) {      
	if ( warnings ) {
	  printf("\nwarning: parameter x%d of op %s is not used. skipping it",
		 l, i->name);
	}
	for ( k = l; k<i->num_vars-1; k++ ) {
	  i->var_types[k] = i->var_types[k+1];
	}
	i->num_vars--;
      } else {
	l++;
      }
    }
    remove_unused_vars_under_CodeNode( &(i->preconds), warnings );
    rename_vars_under_CodeNode( &(i->preconds), i->num_vars );
    remove_unused_vars_under_CodeNode( &(i->conditionals), warnings );
    rename_vars_under_CodeNode( &(i->conditionals), i->num_vars );
  }

  i = gcode_operators;
  while ( i && 
	  i->preconds &&
	  i->preconds->connective == FAL ) {
    if ( warnings ) {
      printf("\nwarning: op %s preconds simplify to FALSE. skipping it.",
	     i->name);
    }
    j = i;
    i = i->next;
    free_CodeOperator( j );
  }
  gcode_operators = i;
  prev = i;
  if ( i ) i = i->next;
  while ( i ) {
    if ( i->preconds &&
	 i->preconds->connective == FAL ) {
      if ( warnings ) {
	printf("\nwarning: op %s preconds simplify to FALSE. skipping it.",
	       i->name);
      }
      prev->next = i->next;
      j = i;
      i = i->next;
      free_CodeOperator( j );
    } else {
      prev = prev->next;
      i = i->next;
    }
  }


  i = gcode_operators;
  while ( i && 
	  ( !(i->conditionals) ||
	    !(i->conditionals->sons) ) ) {
    if ( warnings ) {
      printf("\nwarning: op %s has no effects. skipping it.",
	     i->name);
    }
    j = i;
    i = i->next;
    free_CodeOperator( j );
  }
  gcode_operators = i;
  prev = i;
  if ( i ) i = i->next;
  while ( i ) {
    if ( !(i->conditionals) ||
	 !(i->conditionals->sons) ) {
      if ( warnings ) {
	printf("\nwarning: op %s has no effects. skipping it.",
	       i->name);
      }
      prev->next = i->next;
      j = i;
      i = i->next;
      free_CodeOperator( j );
    } else {
      prev = prev->next;
      i = i->next;
    }
  }

  i = gcode_operators;
  while ( i && 
	  has_contradicting_unconditional( i->conditionals ) ) {
    if ( warnings ) {
      printf("\nwarning: op %s has contradicting unconditional effect. skipping it.",
	     i->name);
    }
    j = i;
    i = i->next;
    free_CodeOperator( j );
  }
  gcode_operators = i;
  prev = i;
  if ( i ) i = i->next;
  while ( i ) {
    if ( has_contradicting_unconditional( i->conditionals ) ) {
      if ( warnings ) {
	printf("\nwarning: op %s has contradicting unconditional effect. skipping it.",
	       i->name);
      }
      prev->next = i->next;
      j = i;
      i = i->next;
      free_CodeOperator( j );
    } else {
      prev = prev->next;
      i = i->next;
    }
  }

}



void simplify_all_inst_CodeOperators( void )

{

  CodeOperator *i, *j, *prev;
  CodeNode *n, *nn;

  for ( i = ginst_code_operators; i; i = i->next ) {
    simplify_condition_CodeNode( &(i->preconds), FALSE, TRUE );
    if ( i->conditionals ) {
      for ( n = i->conditionals->sons; n; n = n->next ) {
	for ( nn = n; nn->connective != WHEN; nn = nn->sons );
	simplify_condition_CodeNode( &(nn->sons), FALSE, TRUE );
	simplify_condition_CodeNode( &(nn->sons->next), FALSE, FALSE );
      }
      clean_up_effects( &(i->conditionals), FALSE );
    }
  }

  i = ginst_code_operators;
  while ( i && 
	  i->preconds &&
	  i->preconds->connective == FAL ) {
    j = i;
    i = i->next;
    free_CodeOperator( j );
  }
  ginst_code_operators = i;
  prev = i;
  if ( i ) i = i->next;
  while ( i ) {
    if ( i->preconds &&
	 i->preconds->connective == FAL ) {
      prev->next = i->next;
      j = i;
      i = i->next;
      free_CodeOperator( j );
    } else {
      prev = prev->next;
      i = i->next;
    }
  }


  i = ginst_code_operators;
  while ( i && 
	  ( !(i->conditionals) ||
	    !(i->conditionals->sons) ) ) {
    j = i;
    i = i->next;
    free_CodeOperator( j );
  }
  ginst_code_operators = i;
  prev = i;
  if ( i ) i = i->next;
  while ( i ) {
    if ( !(i->conditionals) ||
	 !(i->conditionals->sons) ) {
      prev->next = i->next;
      j = i;
      i = i->next;
      free_CodeOperator( j );
    } else {
      prev = prev->next;
      i = i->next;
    }
  }

  i = ginst_code_operators;