cff.gz_Fast Forward_规划器

/* * THIS SOURCE CODE IS SUPPLIED ``AS IS'' WITHOUT WARRANTY OF ANY KIND, * AND ITS AUTHOR AND THE JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH * (JAIR) AND JAIR'S PUBLISHERS AND DISTRIBUTORS, DISCLAIM ANY AND ALL * WARRANTIES, INCLUDING BUT NOT LIMITED TO ANY IMPLIED * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, AND * ANY WARRANTIES OR NON INFRINGEMENT. THE USER ASSUMES ALL LIABILITY AND * RESPONSIBILITY FOR USE OF THIS SOURCE CODE, AND NEITHER THE AUTHOR NOR * JAIR, NOR JAIR'S PUBLISHERS AND DISTRIBUTORS, WILL BE LIABLE FOR * DAMAGES OF ANY KIND RESULTING FROM ITS USE. Without limiting the * generality of the foregoing, neither the author, nor JAIR, nor JAIR's * publishers and distributors, warrant that the Source Code will be * error-free, will operate without interruption, or will meet the needs * of the user. */ /********************************************************************* * File: relax.c * Description: this file handles the relaxed planning problem, i.e., * the code is responsible for the heuristic evaluation * of states during search. * * --- THE HEART PEACE OF THE FF PLANNER ! --- * * - fast (time critical) computation of the relaxed fixpoint * - extraction of as short as possible plans, without search * * * * ----- UPDATED VERSION TO HANDLE CONFORMANT SEMANTICS ----- * * * * Author: Joerg Hoffmann 2002 * *********************************************************************/ #include "ff.h" #include "output.h" #include "memory.h" #include "relax.h" #include "search.h" #include "state_transitions.h" /* local globals */ /* in agenda driven algorithm, the current set of goals is this */ State lcurrent_goals; /* fixpoint */ int *lF; int lnum_F; int *lE; int lnum_E; int *lch_E; int lnum_ch_E; int *l0P_E; int lnum_0P_E; /* for get applicable actions */ int *lch_O; int lnum_ch_O; int *l0P_O; int lnum_0P_O; /* conformant part: the ``temporal implication graph'' */ UftNode **lU; int *lnum_U; /* the U graph is built for the whole path to the state; * this int here is the number of the U layer that corresponds * to the state itself, ie to the first rplangraph layer. */ int lpath_U_length; /* 1P extraction */ int **lgoals_at; int *lnum_goals_at; int *lch_F; int lnum_ch_F; int *lused_O; int lnum_used_O; int lh; int lMAX_PATHNODES; /* CNF time of vars in S -- for ini_ors == 5 */ int lStime; /* clauses for reasoning about initial formula implications */ TimedLiteral **lr_clauses; int *lr_clause_length; int lr_num_clauses; /* we use our own codes in the CNF, to avoid confusion with this other shit I programmed * 2 years ago */ int *lr_codes;/* maps a fact at time 0 to its r-internal code */ int lr_num_c;/* nr. of codes */ int *lr_cf;/* maps a r-internal code to the resp. fact */ /* for naive DP implementation */ int *lr_assigned; /* stores the current DP decisions including unit propagations. */ int *lr_decision_stack; int lr_num_decision_stack; /* for each possible ft code, a pointer to connected dynamic list * of member elements, ie the clauses in which it participates, * positive and negative. */ MemberList_pointer *lr_pos_c_in_clause_start; MemberList_pointer *lr_pos_c_in_clause_end; MemberList_pointer *lr_neg_c_in_clause_start; MemberList_pointer *lr_neg_c_in_clause_end; /************************************* * helper, for -1 == INFINITY method * *************************************/ Bool LESS( int a, int b ) { if ( a == INFINITY ) { return FALSE; } if ( b == INFINITY ) { return TRUE; } return ( a < b ? TRUE : FALSE ); } /*********************************** * FUNCTIONS ACCESSED FROM OUTSIDE * ***********************************/ Bool contains_goal( State *S, State *current_goals ) { int i, j; for ( i = 0; i < current_goals->num_F; i++ ) { for ( j = 0; j < S->num_F; j++ ) { if ( S->F[j] == current_goals->F[i] ) break; } if ( j == S->num_F ) { return FALSE; } } return TRUE; } void initialize_relax( void ) { int i, j, maxcl, m, ff, min, min_i; Bool *had; make_state( &lcurrent_goals, gnum_ft_conn ); /* need to do this here as we do not call real gH setup fn */ gH = ( int * ) calloc( gnum_op_conn, sizeof( int ) ); gnum_H = 0; gA = ( int * ) calloc( gnum_op_conn, sizeof( int ) ); gnum_A = 0; /* the temporal implication graph between * unknown facts. */ lU = ( UftNode ** ) calloc( RELAXED_STEPS + MAX_PLAN_LENGTH, sizeof( UftNode * ) ); lnum_U = ( int * ) calloc( RELAXED_STEPS + MAX_PLAN_LENGTH, sizeof( int ) ); for ( i = 0; i < RELAXED_STEPS + MAX_PLAN_LENGTH; i++ ) { lU[i] = ( UftNode * ) calloc( gmax_U, sizeof( UftNode ) ); lnum_U[i] = 0; for ( j = 0; j < gmax_U; j++ ) { lU[i][j].num_in = 0; } } lMAX_PATHNODES = (RELAXED_STEPS + MAX_PLAN_LENGTH) * gmax_U; /* rp stuff */ lF = ( int * ) calloc( gnum_ft_conn, sizeof( int ) ); lE = ( int * ) calloc( gnum_ef_conn, sizeof( int ) ); lch_E = ( int * ) calloc( gnum_ef_conn, sizeof( int ) ); l0P_E = ( int * ) calloc( gnum_ef_conn, sizeof( int ) ); /* get A stuff */ l0P_O = ( int * ) calloc( gnum_op_conn, sizeof( int ) ); lch_O = ( int * ) calloc( gnum_ef_conn, sizeof( int ) ); /* various initializations */ lnum_0P_E = 0; for ( i = 0; i < gnum_ef_conn; i++ ) { gef_conn[i].level = INFINITY; gef_conn[i].in_E = FALSE; gef_conn[i].num_active_PCs = 0; gef_conn[i].ch = FALSE; if ( gef_conn[i].num_PC == 0 ) { l0P_E[lnum_0P_E++] = i; } } lnum_0P_O = 0; for ( i = 0; i < gnum_op_conn; i++ ) { gop_conn[i].is_in_A = FALSE; gop_conn[i].is_in_H = FALSE; gop_conn[i].ch = FALSE; if ( gop_conn[i].num_P == 0 ) { l0P_O[lnum_0P_O++] = i; } } for ( i = 0; i < gnum_ft_conn; i++ ) { gft_conn[i].level = INFINITY; gft_conn[i].in_F = FALSE; } /* Mar04: * CREATE SAT FORMULA TO BE USED FOR INITIAL IMPLIES DISJUNCTION CHECKING!! * (if needed) * * (for h == 0 we do this just to be able to use the same pieces of code... * can't be critical for performance...) */ if ( gcmd_line.heuristic == 0 || gcmd_line.heuristic == 1 ) { /* do it Baby */ /* get the memory */ maxcl = gnum_initial_or + gnum_ft_conn; lr_clauses = ( TimedLiteral ** ) calloc( maxcl, sizeof( TimedLiteral * ) ); lr_clause_length = ( int * ) calloc( maxcl, sizeof( int ) ); for ( i = 0; i < maxcl; i++ ) { lr_clauses[i] = ( TimedLiteral * ) calloc( gmax_literals, sizeof( TimedLiteral ) ); lr_clause_length[i] = 0; } lr_num_clauses = 0; lr_codes = ( int * ) calloc( gnum_ft_conn, sizeof( int ) ); lr_cf = ( int * ) calloc( gnum_ft_conn + 1, sizeof( int ) ); lr_num_c = 0; for ( i = 0; i < gnum_ft_conn; i++ ) { lr_codes[i] = -1; } lr_assigned = ( int * ) calloc( gnum_ft_conn + 1, sizeof( int ) ); for ( i = 0; i < gnum_ft_conn + 1; i++ ) { lr_assigned[i] = -1; } lr_decision_stack = ( int * ) calloc( gnum_ft_conn, sizeof( int ) ); lr_pos_c_in_clause_start = ( MemberList_pointer * ) calloc( gnum_ft_conn + 1, sizeof( MemberList_pointer ) ); lr_pos_c_in_clause_end = ( MemberList_pointer * ) calloc( gnum_ft_conn + 1, sizeof( MemberList_pointer ) ); lr_neg_c_in_clause_start = ( MemberList_pointer * ) calloc( gnum_ft_conn + 1, sizeof( MemberList_pointer ) ); lr_neg_c_in_clause_end = ( MemberList_pointer * ) calloc( gnum_ft_conn + 1, sizeof( MemberList_pointer ) ); for ( i = 0; i <= gnum_ft_conn; i++ ) { lr_pos_c_in_clause_start[i] = NULL; lr_neg_c_in_clause_start[i] = NULL; lr_pos_c_in_clause_end[i] = NULL; lr_neg_c_in_clause_end[i] = NULL; }