an agent aims to find a path on a hexagonal map with initial state s0 in the center and goal state s⋆ at the bottom as depicted below. The map is parametrized by the distance n ≥ 1 from s0 to any of the border cells (n = 3 in the depicted example). The agent can move from its current cell to any of the 6 adjacent cells,

enter image description here

How can we find the number of node expansions performed by bfs without duplicate detection, and with duplicated detection as a function of n.

I know that the branching factor for the map would be 6 because the agent can move in 6 directions, and for a depth of k, we get O(b^k) = 6^n without duplicate detection, but what is the number of node expansion with duplicate detection with bfs.


At first we must define what the OP has asked. He do not want to know, how an agent has to be programmed which acts intelligently in a hexagonal map, instead the question is about a meta-agent which is able to learn the behavior of other agents. The easiest form in doing so is a plan recognition. That means, the agent's actions are recorded, his branching strategy is parsed and as a result the node expansion ratio can be determined.

Plan recognition is equal to case-based learning. At first, the raw data of an agent needs to be recorded. Then the data gets annotated by a semantic tagger and a model is used for get the branching strategy. The model is also not about "Breadth first search" itself, but the question is about how to recognize a "Breadth first search" strategy performed by an agent. One option is to use a neural network for learning different models from the past, the other option is to create such a model manually with an ontology. In the easiest form, the parser counts the number of performed branches and calculates the ratio. A possible application would be a crawler detection algorithm which calculates the recursiveness of a bot.

  • $\begingroup$ Thanks for the response, I just need to know what is the number of node expansion using Breadth first search with duplicate detection. $\endgroup$ – akano1 Jun 5 '18 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.