trsing’s diary

勉強、読んだ本、仕事で調べたこととかのメモ。

Conflict-based searchメモ

はじめに

お仕事で群制御せななあという感じになってきたので調べてるとMAPFという分野(?)がそれっぽく、 この分野ではCBSを知ってて当然みたいな感触。 のわりに日本語での解説を見つけられなかったので元の論文(多分)を読んだ。

元論文

https://www.sciencedirect.com/science/article/pii/S0004370214001386

CBSだけじゃなくてMAPFの難しさや先行事例についてもざっと説明してくれてるでとてもありがたかった。

今回のメモには書かないけどCBSで最適解が得られることの証明やCBSの欠点とその緩和方法(MA-CBS)についても書いてる。ありがたや。

前提知識

ヒューリスティック探索の基礎(?)。次の資料によくまとまってる。日本語。うれしい。

https://jinnaiyuu.github.io/pdf/textbook.pdf

MAPFについて

multi-agent pathfinding。 複数のエージェントが衝突せずにそれぞれのゴールに到達するまでのパスを求める。 CBSは最適MAPFアルゴリズム

問題定義

  • 入力

    • グラフ: G(V, E)
    • k個のエージェント: a_1,a_2,\dots,a_k
    • 各エージェントのスタート位置とゴール位置: start_i, goal_i
  • 出力
    エージェントが衝突せずにゴールに到着するパス(スタート位置からゴールに到着するまでの一連のアクション)

  • 制約

    • 衝突禁止。同時刻に一つの頂点に2つ以上のエージェントが存在することはできない。
    • すれ違い禁止。連続した時間ステップで2つ以上のエージェントがエッジを横切ることはできない。
  • コスト関数 今回使用するコスト関数はSum-of-costs。 各エージェントがゴールに到着して停止1するまでにかかった時間の総和。

MAPFの難しさ

探索空間が指数関数的に増加する。 1ステップでO(分岐係数^{エージェント数})。 格子型のマップ2でエージェント数が20なら5^{20}=95,367,431,640,625。1ステップでこれ。やってられっか。

CBSアルゴリズム

二つのレベル(High,Low)の処理で構成される。
HighレベルはCT(constraint tree)を探索する。衝突のないnodeが見つかったらそれをgoalとして終了。
Lowレベルは対象エージェントa_iに対するパスを生成する。

constraint tree

二分木3。各ノードは次の情報から構成される。

  • 制約集合(N.constraints):各制約は(a_i, v, t) (時刻tでエージェントa_iに頂点vにいることを禁止)または(a_i, v_1, v_2, t) (時刻tでエージェントa_iv_1からv_2への移動を禁止。すれ違いを防ぐ)。 親ノードのconstraintsに制約を一つ加えたものを持つ。4
  • 解(N.solution):それぞれのエージェントに対するパス。 パスは制約(N.constraints)を満たす。5
  • 総コスト(N.cost):解(N.solution)のコスト。それぞれのパスのコストの総和。ノードのf-value(論文の1.や3.3.1.参照)。

Highレベル

CTに対し、最良優先探索を行う。評価基準はコスト(N.cost)。コストが同じ場合は衝突が少ない方を優先する。 解(N.solution)を検証し、衝突がある場合は衝突を防ぐ制約を追加した子ノードを生成し処理を続ける。 衝突がない場合はノードNをgoalとし処理を終了する。

Lowレベル

対象エージェントa_iと制約集合を受け取り、エージェントa_iに対して制約を満たす最適パスを生成する。 エージェントa_i以外は存在しないものとして探索する。 論文ではA*を使用しているがsingle-agent pathfindingアルゴリズムを使用できる。

疑似コード

python風。

root = Node()
root.constraints = 空集合 # 制約なし
root.solution = 各エージェントのパス # 制約なしでlow level処理したもの
root.cost = root.solutionのコスト
open.put(root)
while not open.empty():
    node = openリスト中の一番コスト低いやつ
    conflicts = node.solutionを検証 # 衝突(a_i,a_j,v,t)のリストを得られるとする
    if 衝突無し: # 衝突がないのでgoal
        return node.solution
    conflict = conflictsの最初の衝突
    for agent in conflict: # a_i, a_jに制約を加えた子ノードを作る
        child = Node()
        child.constraints = node.constraintsに(agent, v, t)を加えたもの
        child.solution = node.solution
        child.solution[agent] = agentのパスを更新 # agentについて制約child.constraintsでlow level処理したもの
        child.cost = child.solutionのコスト
        if 解あり:
            open.put(child)

その他

お仕事の要件に近いのMAPD(Multi-Agent Pickup and Delivery)だわ。


  1. ゴールに居続ける。他の頂点に移動しない。
  2. 上下左右待機で分岐係数5
  3. 簡易化のため。二分木じゃなくてもいい。
  4. 親をたどれば制約を追えるので追加した制約のみ保持しておけばよい。
  5. 追加した制約の対象となるエージェントのパスのみ更新すればよい。対象でないエージェントのパスは変わらないため。

SSLを無視する設定

経緯

情シスからセキュリティ強化のお知らせ。git cloneやらpipやらで証明書のエラーが出るようになったので問い合わせると証明書無視する方向で何とかしろとのお返事。ので証明書無視する設定とか。

証明書を無視する設定

git

GIT_SSL_NO_VERIFY=1 git clone https://github.https://github.com/hoge/hoge.git

qiita.com

GIT_SSL_NO_VERIFY は、SSL証明書の検証を行わないようにGitへ指示します。 これは、GitリポジトリHTTPS経由で利用するために自己署名証明書を使っている場合や、Gitサーバーのセットアップ中で正式な証明書のインストールが完了していない場合などに必要になります。

git-scm.com

pip

pip --trusted-host pypi.python.org --trusted-host files.pythonhosted.org --trusted-host pypi.org install <ライブラリ名...>

tex2e.github.io

Mark this host or host:port pair as trusted, even though it does not have valid or any HTTPS.

pip.pypa.io

vs codeのupdate

/etc/wgetrccheck_certificate = offを追加

stackoverflow.com

If this is set to off, the server certificate is not checked against the specified client authorities. The default is “on”. The same as ‘--check-certificate’.

www.gnu.org

vs codeの設定ではなくwgetの設定なので注意。

curl

curl --insecure https://192.168.1.2

linuxfan.info

By default, every secure connection curl makes is verified to be secure before the transfer takes place. This option makes curl skip the verification step and proceed without checking.

curl.se

感想

セキュリティ強化でSSLインスペクションを採用したっぽい。その結果証明書無視することになったけどこれセキュリティ強化になるのかな?

その他

開発環境損を大事にする転職先募集先です。

Jetson Orinでpyrealsense2を使う

これ

github.com

補足

cmakeのバージョンに注意。上記コメントでは3.13。どのバージョンからかPYTHON_EXECUTABLEの取り扱いが変わってるっぽい(PYTHON_EXECUTABLE->Python_EXECUTABLE?よくわからない…)

追記

cmake 3.25.2でのビルド結果

librealsense 2.54.1
問題なくビルドできた(make -j4まで完了)

librealsense 2.38.1
cmakeでエラー。Could NOT find Python

librealsense 2.38.1でオプションを-DPYTHON_EXECUTABLE->-DPython_EXECUTABLE
問題なくビルドできた(make -j4まで完了)

ros noeticのmap_serverでマップを変更する

change_map serviceを使う。

ros wiki

amclを使っている場合はuse_map_topictrueにしておく。

ソースコード

      //Change the currently published map
      change_map_srv_ = nh_.advertiseService("change_map", &MapServer::changeMapCallback, this);
    bool changeMapCallback(nav_msgs::LoadMap::Request  &request,
                           nav_msgs::LoadMap::Response &response )
    {
      if (loadMapFromYaml(request.map_url))
      {
        response.result = response.RESULT_SUCCESS;
        ROS_INFO("Changed map to %s", request.map_url.c_str());
      }
      else
      {
        response.result = response.RESULT_UNDEFINED_FAILURE;
      }
      return true;
    }

その他

パッケージは更新されててもros wikiは更新されてないのがそれなりにあるっぽい。amclもパラメータ増えてるし。

ros noeticのdwa_local_plannerでlatch_xy_goal_torelanceを設定する

ros wikiでは

ros wiki

となっているが、<name>は無視して設定する。

ソースコード

latch_xy_goal_torelanceを使用しているLatchedStopRotateControllerdwa_planner_ros.hで宣言。引数ないのでnameは設定されない。

base_local_planner::LatchedStopRotateController latchedStopRotateController_;
LatchedStopRotateController::LatchedStopRotateController(const std::string& name) {
  ros::NodeHandle private_nh("~/" + name);
  private_nh.param("latch_xy_goal_tolerance", latch_xy_goal_tolerance_, false);

  rotating_to_goal_ = false;
}

補足

global_plan発行時にlatchをリセットしている。周期的に発行している場合は注意。

二回目の正直あるいは磁力線を操るが能力

新型コロナウイルスワクチン予防接種(二回目)メモ

職域接種でモデルナ。一回目よりはきついけど発熱と頭痛とアンブッシュとひどい眠気くらいの軽い副反応で済んだっぽい。用意しておいたポカリとウィダーと解熱剤が役に立った。

8/24

8:30 とりあえず体温を測る。36.8度(平熱)。軽い頭痛と気持ち悪さがあるけどいつものことなのでスルー
10:00 会場で体温を測る(非接触)。36.4度。前回は全く痛くなかったので油断してたらちょっと痛かった
11:00 1h経過。とりあえず体温を測る。36.8度。非接触の信頼度ってどんくらいなんだろ
13:00 ゴールデンカムイおもしろい。気が付くと左腕に痛みが。36.6度
14:30 左腕動かすのが結構きつくなってきた。筋肉痛の範囲だけど。頭痛もあるけどこれは通常範囲。36.7度
17:00 特に変わりなく。いや腕の可動範囲が少し狭くなったような。36.8度
18:00 なんかめっちゃ眠い。36.8度
19:00 ちょっと寒気がするかも?37.0度。おや?おやおやおや?
20:00 足の裏がめっちゃぞわぞわする。そしてなぜか腰が痛い。37.5度。解熱剤(バッファリンプレミアム)投入
20:10 ぞわぞわきえた。一瞬で効いたすご
20:40 37.5度。効いてへんやんけ!
22:00 37.2度。わが軍の勝利かも!
24:00 37.2度。寝る!

8/25

9:30 病みあがりの朝ーって感じのけだるさ&ふわふわ感。と思ったら38.3度。病みあがってねえ。しんどくないから解熱剤はええか。寝よ
12:30 よおねた。気分もすっきりわが軍の完全勝利や。めんどうなのでウィダーごくごく。38.4度。あかんやん。寝よ
14:30 38.3度。下がらん。寝よ
17:00 38.1度。さがんねーな。寝よ
18:00 37.9度。勝利!
19:00 37.7度。頭痛はする
21:00 37.7度。頭痛もかなり軽くなった
22:00 37.6度
24:00 37.3度。閉廷

8/26

8:00 36.8度。平熱。頭痛と腕の痛みははチョットするけどまあ
20:00 36.7度。頭痛はするけどいつものか副反応かわかんねえ

8/27

8:00 36.8度。頭痛が抜けないけどこれくらいなら
9:00 あああ頭痛きっつー無理やこれ仕事休む!鎮痛剤(バッファリンプレミアム)!寝る! 11:00 日常範囲の頭痛になった。けど眠いので寝る

8/28

しんどさなどは全くないけどやたら眠い…12hは寝た

8/29

しんどさなどは全くないけどひたすら眠い…12hは寝た

8/30

眠い…けど仕事か…