/********************************************************************* * File: search_plan.c * Description: contains the machinery necessary to search the graph * * Author: Joerg Hoffmann 1998 * *********************************************************************/ /********************************************************************* * (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.  *********************************************************************//********************************************************************* * * NOTE: the commentaries in this file are all in German, cause these are *       notes that I made for my own use while working on the search *       code, which is really terribly complicated. *  *       If you have problems understanding the code (like I do when I have *       a look at it now), contact me at: *        *       hoffmann@informatik.uni-freiburg.de * *       and I'll be happy to answer your questions, if I can... * **********************************************************************/#include "ipp.h"#include "output.h"#include "utilities.h"#include "memory.h"#include "search_plan.h"#include "memoize.h"#include "wave_front.h"/************************************************** * SIMPLE HELPERS, SHOULD BE MACROS. OFTEN CALLED * **************************************************/void DO_OP( int time, OpNode *op ){  int was_used;  was_used = op->info_at[time-1]->is_used++;  if ( !was_used && gnum_ops_at[time-1] == ARRAY_SIZE ) {    printf( "\n\nipp: increase ARRAY_SIZE( preset value: %d )", ARRAY_SIZE );    exit( 1 );  }  if ( !was_used ) {    gops_at[time-1][gnum_ops_at[time-1]++] = op;    gnum_of_actions_tried++;    if ( op->is_noop ) {      gnum_of_noops_tried++;    }  }}void UNDO_OP( int time, OpNode *op ){  int was_used;  was_used = --op->info_at[time-1]->is_used;  if( !was_used ) {    gops_at[time-1][--gnum_ops_at[time-1]] = NULL;  }}void DO_FT( int time, FtNode *ft, OpNode *op ){  int was_used;  FtNode *neg_ft = ft->positive ? gft_table[NEG_ADR( ft->index )] :    gft_table[ft->index];      if ( !neg_ft || !neg_ft->info_at[time] ) {    return;  }  was_used = ft->info_at[time]->is_goal++;  if ( ( !was_used && gnum_goals_at[time] == ARRAY_SIZE ) ||       ft->info_at[time]->is_goal > ARRAY_SIZE ) {    printf( "\n\nipp: increase ARRAY_SIZE( preset value: %d )", ARRAY_SIZE );    exit( 1 );  }  (ft->info_at[time]->is_goal_for)[ft->info_at[time]->is_goal-1] = op;  if ( !was_used ) {    ggoals_at[time][gnum_goals_at[time]++] = ft;    if ( ft->positive ) {      gpos_goals_vector_at[time][ft->uid_block] |= ft->uid_mask;    } else {      gneg_goals_vector_at[time][ft->uid_block] |= ft->uid_mask;    }  }}void UNDO_FT( int time, FtNode *ft ){  int was_used;  FtNode *neg_ft = ft->positive ? gft_table[NEG_ADR( ft->index )] :    gft_table[ft->index];      if ( !neg_ft || !neg_ft->info_at[time] ) {    return;  }  was_used = --ft->info_at[time]->is_goal;  (ft->info_at[time]->is_goal_for)[ft->info_at[time]->is_goal] = NULL;  if ( !was_used ) {    ggoals_at[time][--gnum_goals_at[time]] = NULL;    if ( ft->positive ) {      gpos_goals_vector_at[time][ft->uid_block] &= ~(ft->uid_mask);    } else {      gneg_goals_vector_at[time][ft->uid_block] &= ~(ft->uid_mask);    }  }}FtNode *NEG_FT( FtNode *ft ){  return ( ft->positive ? gft_table[NEG_ADR( ft->index )] : gft_table[ft->index] );}/********************* * SETTING UP SEARCH * *********************/Bool search_plan( int max_time ){  int i;  Bool result;  Integers *j;  expand( max_time );  /* achtung!! hier muss noch irgendwie die reihenfolge der ziele   * in bezug auf definition im domain file beruecksichtigt werden   */  gnum_goals_at[max_time] = 0;  for ( j = gbit_goal_state->positive->indices; j; j = j->next ) {    DO_FT( max_time, gft_table[j->index], NULL );  }  for ( j = gbit_goal_state->negative->indices; j; j = j->next ) {    DO_FT( max_time, gft_table[NEG_ADR( j->index )], NULL );  }  gnum_ops_at[max_time-1] = 0;  gnum_goals_at[max_time-1] = 0;  result = search( max_time, gnum_goals_at[max_time] - 1);  for ( i=gnum_goals_at[max_time] - 1; i>-1; i-- ) {    UNDO_FT( max_time, ggoals_at[max_time][i] );  }  if ( !result ) memoize( max_time );                          return result;}/******************************** * THE TWO MAIN SEARCH FUNCIONS *         ********************************/Bool search( int time, int curr_index ){  EfEdge *ef_i;  EfNode *ef;  FtNode *ft;  if ( time == 0 ) return TRUE;  if ( curr_index < 0 ) {    if ( !action_set_is_minimal( time ) ) {      return FALSE;    }    return complete_goals_and_search( time );  }  while ( ( ft = ggoals_at[time][curr_index] )->info_at[time]->is_true ) {    curr_index--;    if ( curr_index < 0 ) {      return search( time, -1 );    }  }  if ( ft->noop ) {    if ( try_noop( time, ft, curr_index ) ) {      if ( search( time, curr_index - 1 ) ) {	return TRUE;      }           untry_noop( time, ft );    }  }  for ( ef_i = ft->info_at[time]->adders_pointer; ef_i; ef_i = ef_i->next ) {     ef = ef_i->ef;    if ( !try_ef( time, ef, curr_index ) ) {      continue;    }    if ( search( time, curr_index - 1 ) ) {      return TRUE;    }        untry_ef( time, ef );  }  return FALSE;}Bool complete_goals_and_search( int time ){  int i, j;  OpNode *op;  EfNode *i_ef;  FtEdge *i_ft;  FtNode *ft;  for ( i = 0; i < gnum_ops_at[time-1]; i++ ) {    op = gops_at[time-1][i];    for ( i_ef = op->conditionals; i_ef; i_ef = i_ef->next ) {      /* ALLE effekte, also auch dummys, werden auf schaedlichkeit       * geprueft!!!       */      if ( i_ef->first_occurence > time-1 ) {	/* erst soweit runterspulen, bis wir auf dem richtigen level sind...	 * (zeiger op->conditionals zeigt auf letzten hinzugekommenen	 * effekt...)	 *	 * ACHTUNG: INEFFIZIENT. koennte mit einfachen mitteln direkt	 * drauf zugegriffen werden (op_level_info den korrekten anfang	 * mitspeichern oder so...)	 */	continue;      }      if ( cant_do_conditions( time, i_ef ) ) {	/* effekt hat onehin bedingungen, die nicht mit neuen zielen	 * wahr sein koennen; also gar nicht erst auf schaedlichkeit	 * pruefen.	 *	 * beachte: in exclusivitaet ist widerspruechlichkeit bereits	 * enthalten, also werden hier bereits gewaehlte verhinderungs	 * goals erkannt.	 *	 * ACHTUNG DUMMYS: dummy knoten haben zwar keine explizite exclusivitaet,	 *                 solange sie noch nicht integriert sind,	 *                 (PRINZIPIELL IST AUCH EIGENE BERECHNUNG DENKBAR), aber	 *                 auf widerspruechlichkeit, also insbesondere effekt	 *                 verhinderung wird hier reagiert, da auch dummy	 *                 knoten automatisch exclusiv zu ihrer negation sind.	 */	continue;      }      for ( i_ft = i_ef->effects; i_ft; i_ft = i_ft->next ) {	if ( (ft = NEG_FT( i_ft->ft )) == NULL ||	     !ft->info_at[time] ) {	  /* widersprechendes fact kann kein ziel sein, da (noch)	   * nicht vorhanden auf step time	   */	  continue;	}        if ( !ft->info_at[time]->is_goal && 	     !( ft->info_at[time-1] && ft->info_at[time-1]->is_goal ) ) {	  /* widersprechendes fact kein ziel und 	   * auf neuem step nicht da oder auch kein ziel	   */	  continue;	}	if ( !ft->info_at[time]->is_goal ) {	  /* ist neues ziel: nur einschreiten, falls nicht ausschliesslich	   * ziel fuer op selbst	   */	  for ( j=0; j<ft->info_at[time-1]->is_goal; j++ ) {	    if ( (ft->info_at[time-1]->is_goal_for)[j] != op ) break;	  }	  if ( j == ft->info_at[time-1]->is_goal ) {	    /* fact ist nur widerspruch zu op's eigenen effekten	     */	    continue;	  }	}	/* wir muessen diesen effekt verhindern!!	 *	 * aus uebersichtlichkeitsgruenden sprung in die	 * effekt schleife.	 */	break;      }      if ( !i_ft ) {	/* haben kein schaedliches fact in diesem effekt	 * gefunden! --> naechsten effekt pruefen.	 */	continue;      }      /* der reihe nach versuchen, die bedingungen zu        * verhindern       */      for ( i_ft = i_ef->conditions; i_ft; i_ft = i_ft->next ) {		if ( i_ft->ft->info_at[time-1]->is_goal ) {	  /* conditions sind auf time-1 garantiert da...	   * ACHTUNG!!! wenns spaeter dummys gibt	   *            > kein problem:(?) werden als knoten eingetragen.	   *	   * neue ziele koennen nicht verhindert werden.	   */	  continue;	}		if ( (ft = NEG_FT( i_ft->ft )) == NULL ||	     !ft->info_at[time-1] ) {	  /* widerspruchs fact, also verhinderung, (noch) nicht da	   */	  continue;	}	if ( cant_do_ft( time-1, ft ) ||	     is_deleted( time-1, ft, op ) ) {	  /* widerspruchsbedingung ist exklusiv zu ausgewaehlten	   * zielen oder	   * wird von ausgewaehltem op' != op zerstoert...	   *	   * hier auch moeglich: effekte als used markieren und	   * bei zerstoerung beruecksichtigen!!	   *	   * ebenfalls moeglich: getriggerte effekte beruecksichtigen,	   * solche werden aber spaeter im fixpunkt auch noch erkannt.	   * effizienzfrage...??	   */	  continue;	}	/* HOPPLA: effekt bedingung koennte dummy gewesen sein.	 *         wenn das aber der fall ist, dann ist die negation	 *         WEGEN CWA schon da, also KEIN DUMMY. deshalb	 *         werden hier wie gewuenscht nur nicht-dummys	 *         als ziele eingesetzt!!	 *	 *       OHNE CWA NICHT KORREKT!!!!	 */	DO_FT( time-1, ft, op );  	if ( complete_goals_and_search( time ) ) {	  return TRUE;	}	UNDO_FT( time-1, ft );      }      /* schaedlicher effekt kann hier nicht verhindert werden!       */      return FALSE;    }  }  /* an dieser stelle sind alle ausgewaehlten ops auf nicht -   * schaedlichkeit geprueft.   *   * suche fortsetzen.   */  /* hier nochmal minimalitaets check !! ??   */  if ( !action_set_is_minimal( time ) ) {    return FALSE;  }  if ( memoized( time - 1 ) ) {    return FALSE;  }  if ( time > 1 ) {    gnum_ops_at[time-2] = 0;    gnum_goals_at[time-2] = 0;  }	  if ( search( time - 1, gnum_goals_at[time-1] - 1 ) ) {    return TRUE;  }  memoize( time - 1 );  if ( gsame_as_prev_flag && time == gfirst_full_time + 1 ) {    add_candidate( time - 1 );  }  return FALSE;      }/******************************** * SOPHISTICATED SEARCH HELPERS * ********************************/Bool action_set_is_minimal( int time ){  int i;  Bool result = TRUE;  EfNode *i_ef;  FtEdge *i_ft;  FtNode *neg_ft = NULL;  /* zunaechst werden alle getriggerten effekte eingetragen.   *   * wie ueblich: INEFFIZIENT! besser waere es, explizit ausgewaehlte   * effekte zu markieren, dann braucht man die nicht mehr anzuschauen.   */  for ( i = 0; i < gnum_ops_at[time-1]; i++ ) {    for ( i_ef = gops_at[time-1][i]->conditionals; i_ef; i_ef = i_ef->next ) {      if ( i_ef->first_occurence > time-1 ) {	/* INEFFIZIENT: wie im complete - goals pattern waere es besser,	 * direkt vom op auf die hier vorhandenen effekte zugreifen zu 	 * koennen.	 */	continue;      }      for ( i_ft = i_ef->conditions; i_ft; i_ft = i_ft->next ) {	neg_ft = i_ft->ft->positive ? gft_table[NEG_ADR( i_ft->ft->index )] :	  gft_table[i_ft->ft->index];	if ( neg_ft &&	     neg_ft->info_at[time-1] &&	     !i_ft->ft->info_at[time-1]->is_goal ) {	  break;	}      }      if ( !i_ft ) {	for ( i_ft = i_ef->effects; i_ft; i_ft = i_ft->next ) {	  i_ft->ft->info_at[time]->is_true++;	}      }    }  }  /* wenn es einen op gibt, der kein einziges fact alleine addet, dann