search_plan.c

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

   * ist das set nicht minimal.
   */
  for ( i = 0; i < gnum_ops_at[time-1]; i++ ) {
    if ( gops_at[time-1][i]->is_noop ) {/* special fuer noops */
      if ( gops_at[time-1][i]->preconds->ft->info_at[time]->is_true == 1 ) {
	continue;
      }
    }
    for ( i_ft = gops_at[time-1][i]->unconditional->effects;
	  i_ft; i_ft = i_ft->next ) {/* der unkonditionale rettet ? */
      if ( !i_ft->ft->info_at[time]->is_goal ) continue;
      if ( i_ft->ft->info_at[time]->is_true == 1 ) break;
    }
    if ( i_ft ) {
      continue;
    }
    for ( i_ef = gops_at[time-1][i]->conditionals; i_ef; i_ef = i_ef->next ) {
      /* eigentlich duerften ja nur getriggerte retten...
       * konzeptuell aendern ?
       */
      if ( i_ef->first_occurence > time-1 ) {
	continue;
      }
      for ( i_ft = i_ef->effects; i_ft; i_ft = i_ft->next ) {
	if ( !i_ft->ft->info_at[time]->is_goal ) {
	  continue;
	}
	if ( i_ft->ft->info_at[time]->is_true == 1 ) {
	  break;
	}
      }
      if ( i_ft ) break;
    }
    if ( i_ef ) {/* ein konditionaler hat gerettet */
      continue;
    }
    /* kein rettender effekt wurde gefunden.
     */
    result = FALSE;
    break;
  }


  /* info von oben wieder zuruecksetzen
   */
  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 ) {
	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--;
	}
      }
    }
  }

  return result;


} 





Bool goals_still_possible( int time, int n, OpNode *op )

{

  int i, j, a;
  unsigned int b;
  int e[gop_vector_length_at[time-1]];
  EfEdge *i_ef;

  /* die exclusives aller ausgwaehlten ops und von op zusammen OR en
   */
  for ( i=0; i<gop_vector_length_at[time-1]; i++ ) {
    e[i] &= 0;
    for ( j=0; j<gnum_ops_at[time-1]; j++ ) {
      e[i] |= gops_at[time-1][j]->info_at[time-1]->exclusives[i];
    }
    e[i] |= op->info_at[time-1]->exclusives[i];
  }

  /* alle noch verbleibenden ziele
   */
  for ( i=0; i<n; i++ ){
    if ( ggoals_at[time][i]->noop &&
	 ggoals_at[time][i]->noop->unconditional->first_occurence <= time-1 ) {
      /* geht der noop noch ? */
      a = ggoals_at[time][i]->noop->uid_block;
      b = ggoals_at[time][i]->noop->uid_mask;
      if ( ( e[a] & b ) == 0 ) continue;
    } 
    for ( i_ef = ggoals_at[time][i]->info_at[time]->adders_pointer; 
	  i_ef; i_ef = i_ef->next ) {
      /* geht irgendein effekt noch ?
       */
      if ( ( ( e[i_ef->ef->op->uid_block] ) & ( i_ef->ef->op->uid_mask ) ) == 0 ) {
	break;
      }
    }
    if ( !i_ef ) return FALSE;
  }

  return TRUE;

} 





/**********************************************
 * FUNCIONS FOR TRYING/UNTRYING OPS AND NOOPS *
 **********************************************/









Bool try_noop( int time, FtNode *ft, int curr_index )

{

  OpNode *noop;
  BitVector *a, *b;
  int r;
  FtNode *negft;


  noop = ft->noop;

  if ( noop->unconditional->first_occurence > time-1 ) {
    return FALSE;
  }

  if ( cant_do_op( time, noop ) ) {
    return FALSE; 
  }

  a = ft->info_at[time-1]->pos_exclusives;
  b = ft->info_at[time-1]->neg_exclusives;
  for ( r=0; r<gft_vector_length; r++ ) {
    if ( a[r] & gpos_goals_vector_at[time-1][r] ) return FALSE;
    if ( b[r] & gneg_goals_vector_at[time-1][r] ) return FALSE;
  }

  if ( ft->positive ) {
    negft = gft_table[NEG_ADR( ft->index )];
  } else {
    negft = gft_table[ft->index];
  }

  /* achtung! wenn's negft auf diesem level noch gar nicht gibt, 
   * ist ft automatisch war und braeuchte gar nicht erst in
   * goals at aufgenommen zu werden.
   *
   * muesste man beim new goal einziehen beruecksichtigen.
   */

  if ( negft && negft->info_at[time-1] &&
       negft->info_at[time-1]->is_goal ) {
    return FALSE;
  }

  if ( !goals_still_possible( time, curr_index, noop ) ) {
    return FALSE;
  }

  DO_OP( time, noop );

  DO_FT( time-1, ft, noop );

  ft->info_at[time]->is_true++;

  return TRUE;

}



Bool try_ef( int time, EfNode *ef, int curr_index )

{

  OpNode *op;
  FtEdge *i_ft;
  FtNode *ft;


  if ( ef->info_at[time-1]->is_dummy ) {
    /* das reicht aus, um zu gewaehrleisten, dass KEIN DUMMY ZIEL WIRD.
     * und zwar deswegen, weil keine nicht-dummy-effekte dummy facts
     * benutzen koennen; diese werden in den graph - vorhanden bit strings
     * nicht vermerkt.
     *
     * WICHTIG: das MUSS in BUILD_GRAPH gewaehrleistet werden, d.h. kein
     *          normaler effekt darf dummys benutzen!!
     */
    return FALSE;
  }

  op = ef->op;


  if ( !op->info_at[time-1]->is_used ) {

    if ( cant_do_op( time, op ) ) {
      return FALSE; 
    }

    /* im unterschied zu conditions koennen preconds NICHT
     * von bereits ausgewaehlten ops deleted werden;
     * diese ops sind exclusiv...
     */
    if ( cant_do_preconds( time, ef ) ) {
      return FALSE;
    }

    /* ACHTUNG!! man koennte sowas auch mit noch-nicht-ausgewaehlten 
     * konditionalen effekten machen, die ja onehin getriggert werden!
     *
     * KONSEQUENT HIESSE DAS, EFFEKT -> IS USED EINZUFUEHREN!!!
     */
    for ( i_ft = op->unconditional->effects; i_ft; i_ft = i_ft->next ) {

      if ( (ft = NEG_FT( i_ft->ft )) == NULL ||
	   !ft->info_at[time] ) {
	/* widersprechendes fact (noch) nicht da auf level time
	 */
	continue;
      }

      /* widersprechende neue ziele weil diese effect conditions von
       * ausgewaehlten ops sein koennen (nicht preconds, sonst excl)
       */
      /* widersprechende alte ziele: bei reinem STRIPS waeren alle adder
       * automatisch excl von diesem op; also schlagen alle auswahlen 
       * fehl, dieser op wird spaeter zureuckgenommen.(moeglich, siehe
       * graphplan, aber ineffizient). in unserem fall koennen auch
       * conditionals dieses fact adden, daher explizite abfrage NOETIG!!
       */ 
      if ( ft->info_at[time]->is_goal ||
	   ( ft->info_at[time-1] && ft->info_at[time-1]->is_goal ) ) {
	return FALSE;
      }
    }

    if ( !goals_still_possible( time, curr_index, op ) ) {
      return FALSE;
    }
  }

  if ( ef->conditions && cant_do_conditions( time, ef ) ) {
    return FALSE;
  }
  /* der -wird deleted- test; muss nur fuer effektbedingungen
   * ausgefuehrt werden.
   *
   * faengt zur zeit nur uncond deletes ab; man koennte (siehe oben)
   * auf jeden fall AUSGEWAEHLTE EFFEKTE book keeping machen und
   * diese auch ausschliessen, das wird zur zeit erst im fixpunkt
   * gemacht, wo es keine moeglichkeit zur verhinderung gibt.
   *
   * auch getriggerte effs moeglich, aber wahrscheinlich ineffizient
   *
   * SPAETER HIER DUMMY - TEST!!
   */
  for ( i_ft = ef->conditions; i_ft; i_ft = i_ft->next ) {
    if ( is_deleted( time-1, i_ft->ft, op  ) ) {
      return FALSE;
    }
  }



  DO_OP( time, op );

  for ( i_ft = op->preconds; i_ft; i_ft = i_ft->next ) {
    DO_FT( time - 1, i_ft->ft, op );
  }

  for ( i_ft = ef->conditions; i_ft; i_ft = i_ft->next ) {
    DO_FT( time - 1, i_ft->ft, op );
  }


  for ( i_ft = op->unconditional->effects; i_ft; i_ft = i_ft->next ) {
    i_ft->ft->info_at[time]->is_true++;
  }

  return TRUE;
  
}



void untry_noop( int time, FtNode *ft )

{

  ft->info_at[time]->is_true--;

  UNDO_FT( time - 1, ft );

  UNDO_OP( time, ft->noop );

}



void untry_ef( int time, EfNode *ef )

{

  FtEdge *i_ft;
  OpNode *op = ef->op;

  for ( i_ft = op->unconditional->effects; i_ft; i_ft = i_ft->next ) {
    i_ft->ft->info_at[time]->is_true--;
  }

  for ( i_ft = ef->conditions; i_ft; i_ft = i_ft->next ) {
    UNDO_FT( time - 1, i_ft->ft );
  }

  for ( i_ft = ef->op->preconds; i_ft; i_ft = i_ft->next ) {
    UNDO_FT( time - 1, i_ft->ft );
  }


  UNDO_OP( time, ef->op );

}








/***************************************************
 * HELPERS ON GOAL / OP PROPERTIES AT SEARCH STAGE *
 ***************************************************/









Bool cant_do_ft( int time, FtNode *ft )

{

  int r;
  BitVector *a, *b;

  a = ft->info_at[time]->pos_exclusives;
  b = ft->info_at[time]->neg_exclusives;
  for ( r=0; r<gft_vector_length; r++ ) {
    if ( a[r] & gpos_goals_vector_at[time][r] ) return TRUE;
    if ( b[r] & gneg_goals_vector_at[time][r] ) return TRUE;
  }

  return FALSE;

}

 
Bool is_deleted( int time, FtNode *ft, OpNode *op )

{

  int i;
  OpNode *op2;
  FtNode *ft2;
  FtEdge *i_ft;

  for ( i=0; i<gnum_ops_at[time]; i++ ) {
    op2 = gops_at[time][i];

    if ( op2 == op ) {
      continue;
    }

    for ( i_ft = op2->unconditional->effects; i_ft; i_ft = i_ft->next ) { 
      if ( (ft2 = NEG_FT( i_ft->ft)) != ft ) {
	/* beinhaltet den fall, dass ft2 == NULL
	 */
	continue;
      }
      return TRUE;
    }

    /* ACHTUNG!!! hier koennte man 1. noch eine AUSGEWAEHLTE
     * COND. EFFEKTE - behandlung einbauen, d.h. auch cond. zerstoerung
     * ohne grossen mehraufwand feststellen;
     *
     * 2. GETRIGGERTE effekte suchen; dies wird allerdings     
     * spaeter im fixpunkt gefunden, durch
     * 'leere verhinderungsliste'.
     * also nicht noetig, fragt sich, was schneller ist.
     */
  }

  return FALSE;

}



Bool cant_do_op( int time, OpNode *op )

{

  int i;

  for ( i=0; i<gnum_ops_at[time-1]; i++ ) {
    if ( (gops_at[time-1][i]->info_at[time-1]->exclusives)[op->uid_block]
	 & op->uid_mask ) {
      return TRUE;
    }
  }

  return FALSE;

}


Bool cant_do_preconds( int time, EfNode *ef )

{

  BitVector *p = ef->op->unconditional->info_at[time-1]->cond_pos_exclusives;
  BitVector *n = ef->op->unconditional->info_at[time-1]->cond_neg_exclusives;
  BitVector *b, *c;
  int r;
  OpNode *op = ef->op;
  FtEdge *i;

  if ( !p ) {
    p = new_excl_bit_vector( gft_vector_length );
    n = new_excl_bit_vector( gft_vector_length );
    for ( i = op->preconds; i; i = i->next ) {
      b = i->ft->info_at[time-1]->pos_exclusives;
      c = i->ft->info_at[time-1]->neg_exclusives;
      for ( r = 0; r < gft_vector_length; r++ ) {
	p[r] |= b[r];
	n[r] |= c[r];
      }
    }
    op->unconditional->info_at[time-1]->cond_pos_exclusives = p;
    op->unconditional->info_at[time-1]->cond_neg_exclusives = n;
  }

  for ( r=0; r<gft_vector_length; r++ ) {
    if ( gpos_goals_vector_at[time-1][r] & p[r] ) {
      return TRUE;
    }
    if ( gneg_goals_vector_at[time-1][r] & n[r] ) {
      return TRUE;
    }
  }
  return FALSE;

}
 

  
Bool cant_do_conditions( int time, EfNode *ef )

{

  BitVector *p = ef->info_at[time-1]->cond_pos_exclusives;
  BitVector *n = ef->info_at[time-1]->cond_neg_exclusives;
  BitVector *b, *c;
  int r;
  FtEdge *i;

  if ( !p ) {
    p = new_excl_bit_vector( gft_vector_length );
    n = new_excl_bit_vector( gft_vector_length );
    for ( i = ef->conditions; i; i = i->next ) {
      b = i->ft->info_at[time-1]->pos_exclusives;
      c = i->ft->info_at[time-1]->neg_exclusives;
      for ( r = 0; r < gft_vector_length; r++ ) {
	p[r] |= b[r];
	n[r] |= c[r];
      }
    }
    ef->info_at[time-1]->cond_pos_exclusives = p;
    ef->info_at[time-1]->cond_neg_exclusives = n;
  }

  for ( r=0; r<gft_vector_length; r++ ) {
    if ( gpos_goals_vector_at[time-1][r] & p[r] ) {
      return TRUE;
    }
    if ( gneg_goals_vector_at[time-1][r] & n[r] ) {
      return TRUE;
    }
  }
  return FALSE;

}
 



  
  


/*******************
 * GENERAL HELPERS * 
 *******************/










void expand( int max_time )

{

  static Bool first = TRUE;
  int i;

  if ( ggoals_at != NULL ) free( ggoals_at );
  ggoals_at = ( FtArray * ) calloc( max_time + 1, sizeof( FtArray ) );
  CHECK_PTR(ggoals_at);
  if ( gnum_goals_at != NULL ) free( gnum_goals_at );
  gnum_goals_at = ( int * ) calloc( max_time + 1, sizeof( int ) );
  CHECK_PTR(gnum_goals_at);
  
  if ( first ) {
    for ( i=0; i<max_time; i++ ) {
      gpos_goals_vector_at[i] = new_bit_vector( gft_vector_length );
      gneg_goals_vector_at[i] = new_bit_vector( gft_vector_length );
    }
    first = FALSE;
  }
  gpos_goals_vector_at[max_time] = new_bit_vector( gft_vector_length );
  gneg_goals_vector_at[max_time] = new_bit_vector( gft_vector_length );

  if ( gops_at != NULL ) free( gops_at );
  gops_at = ( OpArray * ) calloc( max_time, sizeof( OpArray ) );
  CHECK_PTR(gops_at);
  if ( gnum_ops_at != NULL ) free( gnum_ops_at );
  gnum_ops_at = ( int * ) calloc( max_time, sizeof( int ) );
  CHECK_PTR(gnum_ops_at);

}