gggggraziegrazie

graizegrazieさんのやったこと、学んだことを記録する雑記帳です

Branch and Bound(分枝限定法)法

分枝限定法とは、組合せ計画問題で厳密解を求めるための手法の1つです。組合せ計画問題とは、ある関数を最大化するパラメータの組の様に、パラメータの有限個の組み合わせの中から目的を満たす組を求める問題です。分枝限定法は、条件分岐を駆使して問題を部分問題にどんどん分割してきます。これを分枝操作といいます。ある部分問題において、これ以上解を探索する必要がないと判断した(部分問題を解いた)場合、部分問題の分割を止めます。これを限定操作といいます。これにより、分枝限定法は探索時間の削減を図ります。部分問題の解は暫定解と呼ばれ、各部分問題を解いた時点での最良の解と言えます。探索する必要がないと判断する条件は下記の通りです。

  • 既に最適解が得られた
  • 現在の暫定解よりも良い解が得られる可能性がなくなった
  • 許容解が存在しないことがわかった(つまり実行不可能)= その条件分岐が不適当だということがわかった

なお部分問題を解く際、分枝限定法は問題の制約条件を緩和することで、問題を解きやすくします。緩和後の問題は緩和問題と呼ばれます。緩和問題は元の問題の条件を緩和しただけなので、緩和問題の解 \supset 元々の問題の解となります。そのため緩和問題の解を求めた後に修正することで、最終的に元の問題の解を得られることができます(できることが多いそうです)。緩和の例は下記の図に記載の様に、不連続な値域→連続的な値域に変えるのが一般的なようです。

f:id:graziegrazie:20181019040829p:plain
出典:[1]

分枝限定法のフローは、下図のチャートの通りです。
f:id:graziegrazie:20181019035642p:plain

なお分枝限定法を実装する場合、下記を検討する必要があります。

  • 探索
    • どのような順番で部分問題を選ぶか → 一般的なのは最良優先探索(最も良い許容解が得られそうな部分問題を優先)、深さ優先探索(部分問題の深さがより大きい問題を優先)
  • 限定操作
    • 実行不可能性の判定方法
    • 緩和問題の解き方
  • 分枝操作
    • 問題の分解方法

今回は概念の話に終始しましたが、具体例が必要という場合は[3]を見ると良い気がします。

# 参考文献
[1]http://www.ie.u-ryukyu.ac.jp/~e085739/_downloads/H22.Math.Prog.No.7.pdf
[2]http://www.dais.is.tohoku.ac.jp/~shioura/teaching/mp11/mp11-06.pdf
[3]http://dopal.cs.uec.ac.jp/okamotoy/lect/2013/opt/handout05.pdf

github上のプロジェクトをカスタムしてbitbucket上に自分専用プロジェクトとしてコミットする方法

下記のページがわかりやすいです。
簡単に説明すると、まずbitbucket上にからのレポジトリを作り、そこにgithub上のレポジトリをpullします。その上で変更点をadd & commitするという流れです。

Forking a Github repo to Bitbucket · GitHub

プログラムを書く際に注意すべき点

順次追記していきます。

  • プログラムを書く際、関数の引数として与える数字の単位系・座標系は、クラス毎・ファイル毎に揃えよう

単位系・座標系が入り混じると、想定と異なる単位系・座標系で数値を入力し、想定と異なる挙動に悩まされる可能性が高まります。もちろん単体テストをしていれば防げる訳ですが、製品開発をしているならまだしも、研究開発や趣味で書いている場合は中々テストまでは書かないのではないかと思いますので、ご注意ください。

ROSにおけるCMakeLists.txtの書き方

逐次わかったこと、気づいたことを追記していきます。

catkin_package(  # ここには自ら(このCMakeLists.txtが含まれているROS Packageのことを書きます
INCLUDE_DIRS # headerファイルを探しに行く時のルートディレクトリを記載します → 1)へ
LIBRARIES # add_libraryで定義したライブラリ名を列挙します → 2)へ
CATKIN_DEPENDS # あんまりわかっていないので後日....
DEPENDS # あんまりわかっていないので後日....
)

1) INCLUDE_DIRS
例えば"package_name/include/foo/bar.h"というファイルがあります。find_packgeなどで外部の情報を得ない限り、ソースファイルと同じディレクトリのheaderしかincludeできません。しかしINCLUDE_DIRSを定義すれば、定義したパスからも探してくれます。例えば"INCLUDE_DIRS include"と定義すれば、ソースファイルに"#include "と記載すれば、そのheaderは見つかります。少し変えて"INCLUDE_DIRS include/foo"とすれば、"#include "とすれば見つかります。なおINCLUDE_DIRSにパスを書く場合は、CMakeLists.txtからの相対パスを書くか、絶対パスを書く必要があります。

2)LIBRALIES
add_libraryで定義したライブラリ名を列挙することで、他のパッケージがこのパッケージをfind_packageした時、他のパッケージがそのライブラリを使用することができます。そのため、LIBRARIESに間違ってもadd_executableに記載した名前、はたまた存在しない名前を書くと、他のパッケージがfind_packageした時に、"CMake Error at /home/ユーザ名/catkin_ws/devel/share/パッケージ名/cmake/パッケージ名Config.cmake:該当行 (message):
Project 'その他のパッケージ' tried to find library 'ライブラリ名'. The library is neither a target nor built/installed properly. Did you compile project 'floor_plan_matcher'? Did you find_package() it before the subdirectory containing its code is included?"等と表示され、find_packgeが失敗します。ご注意ください。このパッケージが出た場合、find_packageしようとしているパッケージのLIBRARIESの定義を確認してみてください。

PCLの中のGeneralized ICPの使い方

GICPをテストコードを元に使ってみたのですが、うまく収束せず困っていました。そこでgithub上で何かいいサンプルはないかと思って探していたところ、ちょうどよいものがありましたので共有します!

ETH ZurichのAutonomous system labが公開しているrepositryに、robust_point_cloud_registrationというものがあり、GICPなどのwrapperや彼らのオリジナルのregistrationアルゴリズムが提供されています。このrepositryの中のgicp.ccで、GICPのwrapperクラスの実体が書かれています。この実体中の作法通りにパラメータや関数を使うことで、無事にGICPを収束させることができました。ご参考になりましたら幸いです。

github.com

PCL(Point Cloud Library)の使い方が書かれた資料

PointCloudを使ったコードを書く場合、PCLがよく使われるものと思います。サンプルやテストコードを見ることで使い方を知ることはできますが、解説は殆どありません。今回PCLの中のRegistrationについて書かれた論文がありましたので、メモ代わりに記事にしておきます。

実際にPCLのコードを書かれた方も共著に入っているので、内容的には問題ないかと思います。
https://www.ais.uni-bonn.de/papers/RAM_2015_Holz_PCL_Registration_Tutorial.pdf