AI BFS PART I (version ii)

This is a cherry-pick of the substantive commits from PR #296 , to 1.12 branch. Each commit was tested to compile locally.