이전 포스트 요약

EECBS를 정리한지 좀 시간이 지났었는데, 이번 포스트에선 지난번에 이야기 했던 대로 EECBS의 구현체를 보고 실제로 EECBS에서 어떤식으로 High-Level Search에서 노드를 선택하여 확장하고, 계산을 하는지 알아보려고 한다.

구현체 톺아보기

EECBS의 구현체를 보고, 실제로 각 리스트에서 어떤 값을 기반으로 정렬하는지 알아보려고 한다. 우선 eecbs의 구현체에서 현재 확장할 High-Level Node를 선택하는 코드는 아래와 같다.

// choose the best node
cost_lowerbound = max(cleanup_list.top()->getFVal(), cost_lowerbound);
if (focal_list.top()->sum_of_costs <= suboptimality * cost_lowerbound)
{ // return best d
  curr = focal_list.top();
  curr->chosen_from = "focal";
  focal_list.pop();
  cleanup_list.erase(curr->cleanup_handle);
  open_list.erase(curr->open_handle);
}
else if (open_list.top()->sum_of_costs <= suboptimality * cost_lowerbound)
{ // return best f_hat
  curr = open_list.top();
  curr->chosen_from = "open";
  open_list.pop();
  cleanup_list.erase(curr->cleanup_handle);
  focal_list.erase(curr->focal_handle);
}
else
{ // return best f
  curr = cleanup_list.top();
  curr->chosen_from = "cleanup";
  cleanup_list.pop();
  open_list.erase(curr->open_handle);
  if (curr->getFHatVal() <= suboptimality * inadmissible_cost_lowerbound)
    focal_list.erase(curr->focal_handle);
}

사실 이 부분은 앞에서 설명한 EES가 어떤 리스트에서 확장할 노드를 선택하는 기준에 대한 코드이고, 이와 관련된 EES에 대한 내용은 이전 포스트에서 자세히 다루었기 때문에 굳이 볼 필요 없다. 여기서 내가 정말 보려고 한 내용은 앞서서 설명한 리스트 정렬 기준인 $f, \hat{f}, \hat{h}$ 등이 실제로 어떤 값이 사용되는지 이기 때문에 위 코드에서 비교에 사용된 값인, sum_of_costs 변수와 같이 각 리스트가 정렬되는데 사용된 함수와 그에 관련된 멤버변수를 간단하게 알아보려 한다.

sum_of_costs

우선 sum_of_costs가 코드상에서 어떤식으로 구현되는지 확인해보자. sum_of_costs는 ECBSNode.hpp에 구현되어있는 ECBSNode클래스의 멤버 변수로 아래와 같이 선언되어있다.

int sum_of_costs = 0;  // sum of costs of the paths

즉 현재 High-Level Search노드에서 모든 Agent 경로비용의 합이된다. 실제로 아래 코드는 르트 노드를 만들 때와 노드 확장을 위해 새롭게 경로탐색을 한 후 sum_of_costs를 갱신하는 코드이다.

for (auto i : agents)
{
  paths_found_initially[i] = search_engines[i]->findSuboptimalPath(*root, initial_constraints[i], paths, i, 0, suboptimality);
  // 생략
  root->sum_of_costs += (int)paths[i]->size() - 1;
  // 생략
}

bool ECBS::findPathForSingleAgent(ECBSNode*  node, int ag)
{
  clock_t t = clock();
  auto new_path = search_engines[ag]->findSuboptimalPath(*node, initial_constraints[ag], paths, ag, min_f_vals[ag], suboptimality);
  // 생략
  node->sum_of_costs = node->sum_of_costs - (int) paths[ag]->size() + (int) new_path.first.size();
  // 생략
}

위 코드에서 보다시피, sum_of_cost값은 최초에 root상태를 만들때는, 모든 에이전트 경로의 합으로 구해지고, 자식노드를 확장하여, 새롭게 single agent path planning을 진행할 때 마다, 기존의 경로 가중치를 빼고, 새로운 경로의 가중치를 더하는 방식으로 새로운 경로 탐색마다 갱신하여, 각 High-Level Search에서 경로 가중치 합을 계산하게 된다.

cost_to_go

다음으로는 cost_to_go가 어떤방식으로 구해지는 값인지 확인해보자. 우선 해당 변수는 앞선 포스트에서 설명한 Online Learning of the Cost-To-Go에서 소개한 값으로 아래와 같은 함수에 의해 구해지고, 노드를 확장할때 마다 새롭게 online running을 진행하게 된다.

void CBSHeuristic::updateInadmissibleHeuristics(HLNode& curr)
{
  int h = curr.getName() == "CBS Node"? curr.h_val : 0;
  double cost_error = 0, distance_error = 0;
  double c;
  switch (inadmissible_heuristic)
  {
  case heuristics_type::PATH:
    // update errors along the path to the node
    num_of_errors[0] = 0;
    sum_distance_errors[0] = 0;
    sum_cost_errors[0] = 0;
    for (auto ptr = curr.parent; ptr  != nullptr; ptr = ptr->parent)
    {
      if (ptr->fully_expanded)
      {
        num_of_errors[0]++;
        sum_distance_errors[0] += ptr->distance_error;
        sum_cost_errors[0] += ptr->cost_error;
      }
    }
  case heuristics_type::GLOBAL: // Note: there is no "break" in the previous line, so here we compute heuristics for both GLOBAL and PATH
    if (num_of_errors[0] < 1)
    {
      curr.cost_to_go = max(0, curr.getFVal() - curr.getFHatVal()); // ensure that f <= f^
      return;
    }
    if (num_of_errors[0] <= sum_distance_errors[0])
    {
      c =  sum_cost_errors[0] / num_of_errors[0] * 10;
    }
    else
    {
      c = sum_cost_errors[0] / (num_of_errors[0] - sum_distance_errors[0]);
    }
    curr.cost_to_go = h + (int)(curr.distance_to_go * c);
    break;
  case heuristics_type::LOCAL:
    if (std::abs(1 - sum_distance_errors[0]) < 0.001)
      curr.cost_to_go = h + max(0, (int)(curr.distance_to_go) * 1000);
    else
      curr.cost_to_go = h + max(0, (int)(curr.distance_to_go * sum_cost_errors[0] / (1 - sum_distance_errors[0])));
    break;
  case heuristics_type::CONFLICT:
    if (curr.conflicts.empty() && curr.unknownConf.empty())
      return;
    for (const auto& conflict : curr.conflicts)
    {
      int id = conflict->getConflictId();
      cost_error += getCostError(id);
      distance_error += getDistanceError(id);
    }

    cost_error /= (double)(curr.conflicts.size());
    distance_error /= (double)(curr.conflicts.size());
    if ( distance_error >= 1)
      curr.cost_to_go = (int)(curr.distance_to_go * cost_error);
    else
      curr.cost_to_go = (int)(curr.distance_to_go * cost_error / (1 - distance_error));
    curr.cost_to_go = max(min(MAX_COST, curr.cost_to_go), 0);
    curr.cost_to_go += h;
    break;
  default:
    break;
  }
    if (curr.getFVal() > curr.getFHatVal())
        curr.cost_to_go += curr.getFVal() - curr.getFHatVal(); // ensure that f <= f^
}

그렇다면 sum_of_costs는 어떻게 사용될까. 아래 코드는 High-Level Node를 관리하는 리스트의 구현체중 OPEN리스트의 구현체이다. 즉 해당 코드에 따르면 OPEN리스트의 정렬 함수인 $\hat{f}$은

struct compare_node_by_inadmissible_f
{
  bool operator()(const ECBSNode* n1, const ECBSNode* n2) const
  {
    if (n1->sum_of_costs + n1->cost_to_go == n2->sum_of_costs + n2->cost_to_go)
    {
      if (n1->g_val + n1->h_val == n2->g_val + n2->h_val)
      {
        if (n1->distance_to_go == n2->distance_to_go)
        {
          return n1->h_val >= n2->h_val;
        }
        return n1->distance_to_go >= n2->distance_to_go;
      }
      return n1->g_val + n1->h_val >= n2->g_val + n2->h_val;
    }
    return n1->sum_of_costs + n1->cost_to_go >= n2->sum_of_costs + n2->cost_to_go;
  }
};  // used by FOCAL to compare nodes by f^-val (top of the heap has min f^-val)

pairing_heap< ECBSNode*, compare<ECBSNode::compare_node_by_inadmissible_f> >::handle_type open_handle;

후기

내용