planner.cpp

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