planner.cpp

   1 #include "planner.h"
   2 #include "node.h"
   3 #include <iostream>
   4 using namespace std;
   5 using namespace __gnu_cxx;
   6
   7 extern "C" void* executeNode(void* arg);
   8
   9 struct ExecutionStuff {
  10         sem_t* nodes;
  11         sem_t* list;
  12         Node* node;
  13         queue<Node*>* execQueue;
  14 };
  15
  16 Planner::Planner(std::vector<Action> actions, Literals init, Literals goal){
  17         _init = init;
  18         _goal = goal;
  19         _start = new StartNode(_init);
  20         _finish = new EndNode(_goal);
  21         addNode(_start);
  22
  23         for(vector<Action>::iterator action = actions.begin(); action != actions.end(); ++action){
  24                 Action* act = new Action(*action);
  25                 _actions.push_back(act);
  26                 const Literals& effects = act->effects(0);
  27                 for (Literals::const_iterator effect = effects.begin(); effect != effects.end(); ++effect){
  28                         _actionEffects[*effect] = act;
  29                 }
  30         }
  31         makePlan(_finish);
  32 }
  33
  34 Planner::~Planner(){
  35         //Iterating over the remaining nodes and deleting them
  36         for (vector<Node*>::iterator node = _addedNodes.begin(); node != _addedNodes.end(); ++node){
  37                 delete *node;
  38         }
  39         //iterating over the the remaining actions and deleting them
  40         for (vector<Action*>::iterator action = _actions.begin(); action != _actions.end(); ++action){
  41                 delete *action;
  42         }
  43 }
  44
  45
  46 void Planner::makePlan(Node* node){
  47         addNode(node);
  48
  49         const Preconditions& preconds = node->action()->preconditions();
  50
  51         if (preconds.size() == 0){
  52                 //Add the node as a child to start if there are no preconditions
  53                 _start->addChild(node);
  54         }else{
  55                 //iterate over the preconditions
  56                 for (Preconditions::const_iterator precond = preconds.begin(); precond != preconds.end(); ++precond){
  57                         //Check if there is a node with this precondition as an effect
  58                         hash_map<string,Node*>::iterator addedNode = _addedEffects.find(precond->first);
  59                         if(addedNode != _addedEffects.end()){
  60                                 //Use this node if there is one
  61                                 //cerr << "Using already added node for effect " << precond->first << ", on node: " << node->action()->name() << endl;
  62                                 addedNode->second->addChild(node);
  63                         }else {
  64                                 //Check if there is an action which satisfies this effect
  65                                 hash_map<string, Action*>::iterator action = _actionEffects.find(precond->first);
  66                                 if (action != _actionEffects.end()){
  67                                         //Create a new node for the found effect and add the current
  68                                         //one as a child
  69                                         Node* newnode = new Node(action->second);
  70                                         newnode->addChild(node);
  71                                         makePlan(newnode);
  72                                 }else if (precond->second){
  73                                         //No such action found, and since it was a hard preconition
  74                                         //we need to stop here.
  75                                         cerr << "Could not satisfy the effect: " << precond->first << " for: " << node->action()->name() << endl;
  76                                         return;
  77                                 }else{
  78                                         //No action found, but it was a soft precondition, so we can
  79                                         //satisfy it and continue.
  80                                         //cerr << "Could not satisfy the effect: " << precond->first << " for: " << node->action()->name() << endl;
  81                                         node->satisfyCondition(precond->first);
  82                                         _start->addChild(node);
  83                                 }
  84                         }
  85                 }
  86         }
  87 }
  88
  89 void Planner::addNode(Node* node){
  90         const Literals& effects = node->action()->effects(0);
  91         _addedNodes.push_back(node);
  92
  93         //Iterate over the effects for this node and add them to the map.
  94         for (Literals::const_iterator effect = effects.begin(); effect != effects.end(); ++effect){
  95                 _addedEffects[*effect] = node;
  96         }
  97 }
  98
  99
 100 void Planner::execute(){
 101         sem_init(&_nodes, 0, 1);
 102         sem_init(&_list, 0, 1);
 103
 104         //We've "executed" the start node.
 105         _executedNodes.push(_start);
 106         int executions = 1;
 107
 108         //As long as there executed nodes in the queue.
 109         while (executions > 0){
 110                 //Wait for a node to be added to the queue
 111                 sem_wait(&_nodes);
 112                 --executions;
 113
 114                 //Pop the first node from the queue.
 115                 sem_wait(&_list);
 116                 Node* node = _executedNodes.front();
 117                 _executedNodes.pop();
 118                 sem_post(&_list);
 119
 120                 //We don't need to continue if the end node was executed.
 121                 if (node == _finish)
 122                         return;
 123
 124                 vector<Node*> children = node->children();
 125
 126                 //Iterate over the children for this node
 127                 for(vector<Node*>::iterator child = children.begin(); child != children.end(); ++child){
 128                         //Satisfy the preconditions the current node had as effect.
 129                         if ((*child)->satisfyConditions(node->effects())){
 130                                 //If all preconditions were satisified we can create a new thread
 131                                 //and execute this child.
 132                                 ++executions;
 133                                 pthread_attr_t tattr;
 134                                 pthread_t tid;
 135                                 pthread_attr_init(&tattr);
 136                                 pthread_attr_setscope(&tattr, PTHREAD_SCOPE_SYSTEM);
 137                                 //Create a struct object for the thread and add the
 138                                 //needed members to it.
 139                                 ExecutionStuff* es = new ExecutionStuff;
 140                                 es->nodes = &_nodes;
 141                                 es->list = &_list;
 142                                 es->node = *child;
 143                                 es->execQueue = &_executedNodes;
 144                                 pthread_create(&tid, &tattr, executeNode, es);
 145                         }
 146                 }
 147
 148         }
 149         cerr << "Number of nodes: " << _addedNodes.size() << endl;
 150         //Clearing the init vector, effects will be added below.
 151         _goal.clear();
 152         Preconditions goal = _finish->preconditions();
 153         for (Preconditions::const_iterator precond = goal.begin(); precond != goal.end(); ++precond){
 154                 _goal.push_back(precond->first);
 155         }
 156
 157         cout << "Unsatisfied preconditions so far: " << _goal.size() << ": ";
 158         copy(_goal.begin(), _goal.end(), ostream_iterator<string>(cout, " "));
 159         cout << endl;
 160
 161         //iterator for inserting effects at the end of _init
 162         back_insert_iterator<Literals> ii(_init);
 163
 164         //Iterate throu the nodes, to see what's been done
 165         for (vector<Node*>::iterator node = _addedNodes.begin(); node != _addedNodes.end(); ++node){
 166                 if ((*node)->executed()){
 167                         //Node was executed, adding the effects to _init.
 168                         executions++;
 169                         const Literals& effects = (*node)->effects();
 170                         copy(effects.begin(),effects.end(),ii);
 171
 172                         vector<Action*>::iterator action = find(_actions.begin(), _actions.end(), (*node)->action());
 173                         if (action != _actions.end()){
 174                                 //The action can be deleted, since it's already been executed.
 175                                 delete *action;
 176                                 _actions.erase(action);
 177                         }
 178                 }
 179                 //The node is not needed anymore
 180                 delete *node;
 181         }
 182         //Clearing the vectors and maps, since they are obsolete now.
 183         _addedNodes.clear();
 184         _addedEffects.clear();
 185         _actionEffects.clear();
 186
 187         cout << "Effects achieved so far: " << _init.size() << ": ";
 188         copy(_init.begin(), _init.end(), ostream_iterator<string>(cout, " "));
 189         cout << endl;
 190
 191         if (executions <= 1){
 192                 cerr << "Non of the remaining actions could be executed, quiting." << endl;
 193                 return;
 194         }
 195         if (_actions.size() == 0){
 196                 //Nothing left to do, quitting.
 197                 return;
 198         }
 199         //REPLANNING
 200         cout << "Replanning..." << endl;
 201
 202         //Adding the effecs for the remaining actions.
 203         for (vector<Action*>::iterator action = _actions.begin(); action != _actions.end(); ++action){
 204                 const Literals& effects = (*action)->effects(0);
 205                 for (Literals::const_iterator effect = effects.begin(); effect != effects.end(); ++effect){
 206                         _actionEffects[*effect] = *action;
 207                 }
 208         }
 209         _start = new StartNode(_init);
 210         _finish = new EndNode(_goal);
 211         addNode(_start);
 212         makePlan(_finish);
 213         if (_addedNodes.size() <= 2){
 214                 cerr << "No actions to execute, quiting." << endl;
 215                 return;
 216         }
 217         execute();
 218
 219 }
 220 void* executeNode(void* arg){
 221         ExecutionStuff* es = (ExecutionStuff*)arg;
 222
 223         es->node->execute();
 224
 225         sem_wait(es->list);
 226         //Add this node to the queue with executed nodes
 227         es->execQueue->push(es->node);
 228         sem_post(es->list);
 229
 230         //Signal that the node is available.
 231         sem_post(es->nodes);
 232
 233         pthread_exit((void*)0);
 234 }