DFS no solution found

CommonRoad-Search
1

I set the planner to dfs and max_tree_depth to 10000000 in the configuration file.
When running the planner on all 500 scenarios I get

Total number of scenarios:  	       500
Solution found:               	       322
Solution found but invalid:   	         0
Solution not found:           	       151
Exception occurred:           	         0
Time out:                     	        25

How is it possible that 151 solutions were not found? Did DFS really search all trees up to a depth of 10000000 and determine that there is no solution? :smiley:
I wouldn’t mind getting timeouts, but no solution found seems suspicious.

1 Like
2

It has to abort because of cycles.

3

Hi Tom, thanks for pioneering the Q&A of CommonRoad Search this year. The tree depth parameter doesn’t work with DFS. DFS can have an unbounded number of layers of primitives searching in the wrong direction, which gets aborted before running out of resources.