/*********************** Graphplan ************************************** (C) Copyright 1995 Avrim Blum and Merrick Furst 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 CMU make any warranty about the software or its performance. *************************************************************************/ #include #include #include #include #include enum {false, true} boolean; enum {add, del} action_type; typedef struct VERTEX vertex_s, *vertex_t; typedef struct TOKENLIST *string_list; struct EFFECTLIST; typedef struct INCLLIST{/*this looks really stupid. The utility of this object comes from memory locations providing unique labels. */ double prob; /*I store the probability here so it will stored in only one location.*/ struct INCLLIST *next; } *incl_list, incl_list_ele, *incl_ptr; typedef char * token; typedef struct DELLIST{ token item; struct DELLIST *next; struct INCLLIST *with; } *delete_list, delete_list_elt; typedef struct EDGE { vertex_t endpt; incl_list incl;/*If 2 edges of the same operator have a different incl then they are different possibilities of a probabilistic outcome.*/ struct EDGE *next; } edgelist_s, *edgelist_t; /* HERE ARE SOME ARBITRARY VALUES */ #define MAXMAXNODES 1024 /* max number of nodes per layer of graph */ #define NUMINTS 32 /* MAXMAXNODES / 32 */ #define HSIZE 50 /* For simplicity, fix hash table to have size HSIZE */ #define MAX_TOKENS 15 /* max number of tokens in a tokenlist */ #define MAXGOALS 50 /* max size of a goal set */ #define MAXOPS 512 /* max number of non-noops in a time step */ #define max_auto 200 /* arbitrary max #time steps for making graph */ #define MAX_TOKEN_LENGTH 100 /*maximum size of a token*/ typedef unsigned int NeedVec; #define NEEDVECLEN 32 /* to change above, need to make uses of needed_vecs more robust */ /* a vertex in the graph */ struct VERTEX { char *name; int hashval; /* make easier to find in table */ edgelist_t in_edges; edgelist_t out_edges; delete_list del_list; /* names of things you delete (that aren't preconds) */ edgelist_t del_edges; /* pointers (one way) to things you delete */ edgelist_t exclusive; incl_list inclusions; /*probabilistic outcomes which vary together point to elements in this list */ /*A probabilistic outcome is judged to be exclusive of another if they both point to the same element in the exclusions list and don't point to the same element in the inclusions list.*/ int exclusive_vect[NUMINTS]; int used; /* if used, 1+index in array (add 1 to make sure not zero) */ int is_true; /* is it made true */ int marked; /* using this for pairwise value */ int needed; /* am I needed? */ NeedVec needed_vec; /* who am I needed for? */ int heuristic_value;/* used for propagating values backwards */ int uid_block; /* For planning: use uid_mask and uid_block */ unsigned int uid_mask; /* -- unique for time */ int uid; /* redundant but convenient: unique id */ vertex_t prev_time; /* for facts: the fact at prev time step */ vertex_t next_time; /* and next time step */ long rand1; /* random values associated with fact */ int junk; /* use for whatever one wants */ int is_noop; /* is it a NOOP? */ edgelist_t requirements; /* things that we require in order to be useful */ struct VERTEX *next; }; typedef struct PAIR{ int first; int second; } pair; typedef vertex_t goal_arr[MAXGOALS]; typedef vertex_t fact_arr[MAXGOALS]; typedef vertex_t op_arr[MAXOPS]; typedef vertex_t hashtable_t[HSIZE]; typedef vertex_s element_s, *element_t; typedef struct TOKENLIST { token item; struct TOKENLIST *next; } token_list_elt, *token_list; typedef struct FACTLIST { token_list item; struct FACTLIST *next; } fact_list_elt, *fact_list, *precond_list, *param_list; typedef struct PROBDEFLIST { char str[100]; /* string representing this item */ double prob; struct PROBDEFLIST *next; } probdef_list_elt, *probdef_list; typedef struct EFFECTFACTLIST { int action; /* add or del */ fact_list facts; struct EFFECTFACTLIST *next; } effect_fact_list_elt, *effect_fact_list; /*amount by which we allow probabilities to err*/ #define epsilon .00001 /* list of double and string where the doubles should sum to 1 */ typedef struct EFFECTLIST { struct EFFECTFACTLIST *effects;/* some listing of effects */ double prob; /* with this probability of occuring */ token_list defined_prob; /* or this, which will depend on the instantiation*/ struct EFFECTLIST *next; } *effect_list, effect_list_elt; typedef struct INSTLIST { char *const_part; char *var_part; struct INSTLIST *next; } instantiation_s, *instantiation_list; typedef struct OPER { char *name; param_list params; precond_list preconds; effect_list effects; instantiation_list insts; /* use to store the variables */ struct OPER *next; } op_s, *op_list, *op_ptr; /****defines*****/ #define NOT_THERE (-1) #define AUTO (-2) #define SAME 0 #define DIFFERENT (-1) #define PARAM "params" #define PRECOND "preconds" #define EFFECT "effects" #define OPR "operator" #define DELETE "del" #define LISPEXT ".lisp" #define is_const(x) (*(x) != '<') #define is_var(x) (*(x) == '<') #define TOKEN 1 #define LEFT_PAREN 2 #define RIGHT_PAREN 3 #define PROB 4 #define max(x,y) ((x) > (y) ? (x) : (y)) #define min(x,y) ((x) > (y) ? (y) : (x)) #define equal_tokens(x,y) (!strcmp((x),(y))) #define YES 1 #define NO 0 #define NEW_INSTS 2 #define CONNECTOR '_' #define TRUE 1 #define NOOP "noop" #define IS_NOOP(x) ((x)->is_noop) long random(); /* comment this out depending on compiler */ /***********function prototypes: graphplan.c***************/ void propagate_heuristic_values(int maxtime); void setup_utilities(int do_minexp, int max_time); int create_graph(op_list olist, fact_list flist, int totaltime); void create_graph_layer(op_list olist); op_list load_ops(FILE *fp); int load_fact_list(FILE *fp, fact_list *fptr); effect_list load_effect_list(FILE *fp); void make_graph_piece(op_ptr op, int time); void do_operator(hashtable_t htable, fact_list current_facts, op_ptr op, precond_list p, int time); void remove_unneeded_vertices(int time); int can_stop(int time); void make_copy(int time); fact_list useful_facts(op_list ops, fact_list f); void print_cant_do(int time); fact_list load_types(FILE *fp); double get_prob(incl_list e); /***********function prototypes: hash.c********************/ element_s * lookup_from_table(hashtable_t htable, char *key); element_t insert_token_list(hashtable_t htable, token_list t); element_t insert_into_table(hashtable_t htable, char *key); void remove_from_table(hashtable_t htable, element_t elt); edgelist_t insert_edge(edgelist_t e, vertex_t v, incl_list with); element_t get_next(hashtable_t h, int flag); /***********function prototypes: utilities.c****************/ char *make_noop_string(char *str); fact_list make_list_from_htable(hashtable_t h); instantiation_list insert_inst(char *v, char *c, instantiation_list i); int instantiate_into_string(token_list t, instantiation_list inst, char str[], int failflag); void push_back(char bufin[MAX_TOKEN_LENGTH]); /*push a buffer back into the input stream*/ int read_item(FILE *fp, char *str); void make_op_string(op_ptr op, char *str); void do_error(char *s); int equal_facts(token_list f1, token_list f2); void put_in_all_del_edges(hashtable_t harr[], int time); int avoidable(vertex_t op); void print_graph(hashtable_t *fact_arr, hashtable_t *op_arr, int len); void read_initial_comments(FILE *fp); void my_free(void * p); void * my_alloc(int size); void print_alloc(void); void completely_free_fact_list(fact_list l); void free_token_list(token_list l); int compare_and_instantiate(token_list, token_list,instantiation_list); token_list token_list_from_string(char str[]); void set_uid(vertex_t v, int id); /***********function prototypes: planner.c*****************/ double do_plan(int maxtime); void print_info(int len); int try_facts(vertex_t f1, vertex_t f2, int time); /***********others (viewing)**************/ int are_mutex(vertex_t v1, vertex_t v2); /*****************things for hashing in planner ****************/ #define P_HSIZE 8192 /* planner hash table size */ #define P_HASH 8191 /* 111111111111 */ /* #define BVEC_LEN ((MAXNODES - 1)/32 + 1) */ #define BVEC_LEN 32 /* store sets as bit-vectors: two sets equal if same vector at same time */ typedef unsigned int bit_vector[BVEC_LEN]; typedef struct SET_ELT { double util; /* expected utility*/ vertex_t op; /* storing operator too */ bit_vector item; int num; long sum; int time; int linenumber; /* for printing */ struct SET_ELT *next; } *hash_entry; typedef hash_entry set_table[P_HSIZE]; extern set_table the_table; extern int bvec_len; void make_bit_vector(goal_arr a, int len, bit_vector v); /**************vbles**************/ extern int num_deleted; extern int num_created; extern int DEBUG_FLAG; extern int MAXNODES; /* MAXNODES is the maximum number of nodes allowed per level. */ extern int *utilities; extern int util_of_failing;