Open nakane11 opened 2 years ago
@k-okada
First-time contributors need a maintainer to approve running workflows.
Please approve running workflows to run tests.
can you give us small example to reproduce your problem?
I'm using graph-solver
and I don't encounter the weird situation.
(setq gr (instance graph :init))
(dotimes (i 6)
(send gr :add-node (instance node :init (format nil "~A" i))))
(dotimes (i 5)
(send gr :add-arc-from-to
(send gr :node (format nil "~A" i)) (send gr :node (format nil "~A" (incf i)))))
(dotimes (i 4)
(send gr :add-arc-from-to
(send gr :node (format nil "~A" i)) (send gr :node (format nil "~A" (+ i 2)))))
(dotimes (i 3)
(send gr :add-arc-from-to (send gr :node (format nil "~A" (- 5 i))) (send gr :node (format nil "~A" (- 3 i)))))
(send gr :write-to-pdf "test")
(defun test1 ()
(let (sol path1 path2)
(setq sol (instance breadth-first-graph-search-solver :init))
(setq path1 (send sol :solve-by-name gr "0" "5"))
(format t "0->5~%")
(dolist (i path1)
(format t "~A~%" (send i :state)))
(send gr :write-to-pdf "test1_1" path1)
(setq path2 (send sol :solve-by-name gr "0" "3"))
(format t "0->3~%")
(dolist (i path2)
(format t "~A~%" (send i :state)))
(send gr :write-to-pdf "test1_2" path2)))
(defun test2 ()
(let (sol path1 path2)
(setq sol (instance breadth-first-graph-search-solver :init))
(setq path1 (send sol :solve-by-name gr "0" "5"))
(format t "0->5~%")
(dolist (i path1)
(format t "~A~%" (send i :state)))
(send gr :write-to-pdf "test2_1" path1)
(send sol :clear-open-list)
(setq path2 (send sol :solve-by-name gr "0" "3"))
(format t "0->3~%")
(dolist (i path2)
(format t "~A~%" (send i :state)))
(send gr :write-to-pdf "test2_2" path2)))
(test1)
(test2)
9.irteusgl$ 0->5
#<node #X55cc260f0628 0>
#<node #X55cc260f06b8 1>
#<node #X55cc260f07a8 3>
#<node #X55cc260f08b0 5>
0->3
#<node #X55cc260f0628 0>
#<node #X55cc260f06b8 1>
#<node #X55cc260f07a8 3>
#<node #X55cc260f06b8 1>
#<node #X55cc260f07a8 3>
t
10.irteusgl$ 0->5
#<node #X55cc260f0628 0>
#<node #X55cc260f06b8 1>
#<node #X55cc260f07a8 3>
#<node #X55cc260f08b0 5>
0->3
#<node #X55cc260f0628 0>
#<node #X55cc260f06b8 1>
#<node #X55cc260f07a8 3>
t
when you use depth-first-search
, the result is a bit different.
but you are right. the weird behavior can be found in my PC, too.
(setq gr (instance graph :init))
(dotimes (i 6)
(send gr :add-node (instance node :init (format nil "~A" i))))
(dotimes (i 5)
(send gr :add-arc-from-to
(send gr :node (format nil "~A" i)) (send gr :node (format nil "~A" (incf i)))))
(dotimes (i 4)
(send gr :add-arc-from-to
(send gr :node (format nil "~A" i)) (send gr :node (format nil "~A" (+ i 2)))))
(dotimes (i 3)
(send gr :add-arc-from-to (send gr :node (format nil "~A" (- 5 i))) (send gr :node (format nil "~A" (- 3 i)))))
(send gr :write-to-pdf "test")
(defun test1 ()
(let (sol path1 path2)
(setq sol (instance breadth-first-graph-search-solver :init))
(setq path1 (send sol :solve-by-name gr "0" "5"))
(format t "0->5~%")
(dolist (i path1)
(format t "~A~%" (send i :state)))
(send gr :write-to-pdf "test1_1" path1)
(setq path2 (send sol :solve-by-name gr "0" "3"))
(format t "0->3~%")
(dolist (i path2)
(format t "~A~%" (send i :state)))
(send gr :write-to-pdf "test1_2" path2)))
(defun test2 ()
(let (sol path1 path2)
(setq sol (instance breadth-first-graph-search-solver :init))
(setq path1 (send sol :solve-by-name gr "0" "5"))
(format t "0->5~%")
(dolist (i path1)
(format t "~A~%" (send i :state)))
(send gr :write-to-pdf "test2_1" path1)
(send sol :clear-open-list)
(setq path2 (send sol :solve-by-name gr "0" "3"))
(format t "0->3~%")
(dolist (i path2)
(format t "~A~%" (send i :state)))
(send gr :write-to-pdf "test2_2" path2)))
(defun test3 ()
(let (sol path1 path2)
(setq sol (instance depth-first-graph-search-solver :init))
(setq path1 (send sol :solve-by-name gr "0" "5"))
(format t "0->5~%")
(dolist (i path1)
(format t "~A~%" (send i :state)))
(send gr :write-to-pdf "test3_1" path1)
(setq path2 (send sol :solve-by-name gr "0" "3"))
(format t "0->3~%")
(dolist (i path2)
(format t "~A~%" (send i :state)))
(send gr :write-to-pdf "test3_2" path2)))
(defun test4 ()
(let (sol path1 path2)
(setq sol (instance depth-first-graph-search-solver :init))
(setq path1 (send sol :solve-by-name gr "0" "5"))
(format t "0->5~%")
(dolist (i path1)
(format t "~A~%" (send i :state)))
(send gr :write-to-pdf "test4_1" path1)
(send sol :clear-open-list)
(setq path2 (send sol :solve-by-name gr "0" "3"))
(format t "0->3~%")
(dolist (i path2)
(format t "~A~%" (send i :state)))
(send gr :write-to-pdf "test4_2" path2)))
; (test1)
; (test2)
; (test3)
; (test4)
3.irteusgl$ test3
0->5
#<node #X564226c80668 0>
#<node #X564226c806e0 1>
#<node #X564228294d08 3>
#<node #X564228294e10 5>
0->3
#<node #X564226c80668 0>
#<node #X564226c806e0 1>
#<node #X564228294d08 3>
t
4.irteusgl$ test4
0->5
#<node #X564226c80668 0>
#<node #X564226c806e0 1>
#<node #X564228294d08 3>
#<node #X564228294e10 5>
0->3
#<node #X564226c80668 0>
#<node #X564226c806e0 1>
#<node #X564228294d08 3>
t
clear-open-list
)clear-open-list
)もとの実装の意図が謎ですね。
clear-open-listを純粋仮想関数にしていたり、探索に失敗するとclear-open-listするのに成功するとしなかったり。
一度解を見つけたあと、探索時間に余裕があればより良い解を求めて再度探索するanytime algorithmのようなことをするために、あえて前回の探索結果を残して続きから探索するような形にしたかったのかもしれません。
僕が遡れる範囲で一番古いcommitはこれで、この時点ですでに今の実装になっていたため、もとの実装の意図は不明です。 https://github.com/jsk-ros-pkg/euslib/commit/6ce72383e99f9ef48ec8438b076c38ebcd327435
失敗した場合そもそもopen-listが空なのにclear-open-listをしているのは謎です。open-listのaccessorがあるので、探索が終わった時点ではclear-open-listをしない方がよいかと思っています。
続きから探索する場合、再試行する度にstart-nodeが追加されていくのは変な気がします。
bachward compatibilityは保たれませんが初期化してから探索するのを標準にする場合、:solveにresumeのようなkeyがあるとsolve-initをするかしないか分けられると思います。
続きから探索する場合、再試行する度にstart-nodeが追加されていくのは変な気がします。
そうですね。もとの実装に意図があったとしても機能していないと思うので、初期化してから探索するのを標準にしてしまって良いと思います。
私もそれで良いと思います
修正しました
せっかくなので,doc/irtgraph.tex に使い方のサンプルを簡単でいいので書いてくれると助かります @nakane11
docにサンプルを追加しました
Thank you for contributing jskeus documentation
Please check latest documents before merging
PDF version of Japanese jmanual: jmanual.pdf HTML version of Japanese manual: jmanual.html Sphinx (ReST) version of Japanese manual: jmanual.rst
When I call
:solve
more than once, solver does not return correct path because unsearched nodes remain in open-list after solver succeeded last time. By doing:clear-open-list
at first, solver can start graph-search with start-node.