Search as behaviour selection - Artificial Intelligence

We can think of the search process as one of an agent moving around the environment that represents the search space. At each point where there are alternative paths to explore, the agent has to make a decision about which path to explore. Once a particular path has been chosen, then this will lead to a ‘tree’ of future branches. This abstract view of the search process is based on an analogy with exploration of unknown territory by selecting alternative paths. We can extend this abstract view by noting that the search process usually involves behavioural selection rather than just path selection. The agent searches for the sequence of behaviours that when executed will lead to the desired goal. The execution of the behaviours will lead the agent down particular paths as an outcome. We can apply this view of the search process to characterise the three search problems described above.

For example, in the searching mazes problem, the search process is more than just a search for a set of paths that will allow the agent to travel to the exit or centre of the maze. In order to follow the paths, the agent must execute specific behaviours such as turning left and right, moving ahead and turning around. Hence, the search can be characterised instead as a search for the sequence of behaviours that when executed in a specific order will lead to the desired goal. Forward movement needs to be combined with sensing, for example the agent might apply a different behaviour whenever it senses a wall in front of it, or when it finds there is open space in front of it or to its side.

In the Searching Mazes model, in order to illustrate this behavioural approach to characterising the search process, the agents have been given the ability to execute three different reactive behaviours

  1. moving forward,
  2. turning left then moving forward,
  3. turning right then moving forward.

The agents can also execute several different types of forward movement behaviour. These are controllable by two choosers in the Interface:

  1. the move-forward-behaviour;
  2. the move-forward-behaviour-after-turning.

The first defines the forward movement for reactive behaviour first,and the second defines the forward movement for the reactive behaviours.The types of forward movement are as follows:

  1. “Move forward n steps unless hit wall; where the agent moves forward n steps,and n is a number defined by the Interface; variable move-forward-step-amount;
  2. “Move forward until hit wall”, where the agent will keep on moving forward until it hits a wall;
  3. “Move forward until any open space”, where the agent will move forward until there is a wall in the way or there is open space on both sides of it;
  4. “Move forward until open space after side wall”, where the agent will move forward until there is a wall in the way or there is open space after a side wall.

Despite only being able to execute three basic reactive behaviours, the maze-searching agents can exhibit a surprising variety of movements as a result. Figure below captures a few of these in screenshots taken from the Searching Mazes model using breadth first search on the empty maze. Referring to the numbers and letters in the previous paragraph to describe the four configurations: in the top left image, the agents apply behaviours [1](a) and [2](a), both using a step of 10; in the top right image, the behaviours are [1](a), using a step of 1, and [2](b); in the bottom left image, the behaviours are [1](a), using a step of 10, and [2](c); and in the bottom right image, the behaviours are [1](c) and [2](a), using a step of 10.For example, the grid effect in the top left image is caused by the agents repeatedly moving 10 steps in three directions – forward, left and right. How the grid is built up is best seen by continually pressing the go-once button in the Interface at the start of each search.

Screenshots of different movement behaviours for the Searching Mazes model.

different movement behaviours for the Searching Mazes model

The important distinction is that the search as implemented in the Searching Mazes model is not just a search for alternative paths – it is a search for the sequence of behaviours that the agent must execute in order to get to the goal state. This distinction is most apparent in the definition of the expand-paths procedure for the model as shown in NetLogo Code where each “path” being expanded involves the execution of a specific movement behaviour – forward, left-then-forward or right-then-forward.

NetLogo Code The procedure defining how the paths are expanded for the Searching Mazes model.

The other two search problems can also be characterised as a behavioural selection process rather than a path selection process. For the Searching for Kevin Bacon model (see the expand-paths procedure defined in NetLogo Code ), the agents are applying a single behaviour – they ‘look’ around them to sense the surrounding nodes, and then they move to each in turn. In the search process implemented in the model, the behaviour being applied by the agents is the same as each node is treated as equivalent, but there is no reason why we could not vary the search by choosing between behaviours that take into account different properties of the nodes in the network, such as whether it was a super-node or not, or the distance away from adjacent nodes.

In contrast, for the Missionaries and Cannibals model, the behaviour selection process is more apparent. In the model’s expand-paths procedure shown in NetLogo Code, there are five “paths” being expanded. These correspond to the alternative actions of having two missionaries get in the row-boat, two cannibals in the rowboat, one missionary and one cannibal get in the row-boat, one missionary by itself and one cannibal by itself. According to the definition of behaviour described in Section, these actions can be considered as separate behaviours. To further emphasize the behavioural aspect of these actions, let us imagine, for example, a scenario where the missionaries exhibit the peculiar behaviour of never getting in the row-boat by themselves.

We can simulate this by simply commenting out the “expand-path searcher-agent 1 0” line in the expands-path procedure. This results in significantly different searches being performed as a result for each of the search methods, with some of the searches failing while others, such as breadth-first search, perhaps surprisingly, still managing to be successful at finding a solution, albeit different to the previous one. to expand-paths [searcher-agent]

NetLogo Code The procedure defining how the paths are expanded for the Missionaries and Cannibals model.


All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Artificial Intelligence Topics