Computational Models of Human and Animal Cognition

Traveling Sales Pigeons

Problem Formulation

The Traveling Salesperson Problem (TSP) is straightforward - given a set of cities, or goals, a traveling salesperson must visit all of the cities once and then return to the start point via the shortest route possible. Despite the simplicity of this description, the solution to the problem is computationally hard: Although the optimal path for a given configuration of goals (hereafter called “array”) can be obtained by computing the set of all possible routes and selecting the one with shortest total distance, this calculation becomes more taxing as the number of goals (set size) increases because the number of possible routes increases factorially with set size. For example, when required to travel to four distinct goals and return to the start, there are 24 potential routes one could take, but if set size is increased to 10, the number of potential routes is over three million. The development of a tractable algorithm that would determine the optimal route for any arbitrary TSP problem has eluded computer scientists, although approximation algorithms have been developed.

Finding the most efficient route between multiple goals can be important for numerous everyday activities, whether it be a business scheduling deliveries of their product, or an individual navigating between stores or attractions in a new city. Interest in the TSP and the cognitive processes underlying efficient route selection by humans has intensified recently because of the surprising finding that untrained humans perform remarkably close to optimal on pictorial two-dimensional (2D) versions of the TSP (e.g. “paper-and-pencil” tasks), even with a fairly large set size. In fact, the suboptimality of human solutions seems to increase only linearly with increases in the set size, even though the number of possible routes increases factorially with number of nodes. Optimal or near-optimal performance on TSP tasks has been suggested to indicate higher-order problem solving and future-planning abilities, and in the field of neuropsychology, TSP tasks have been used to assess cognitive function and problem-solving abilities in humans. Thus, understanding human and animal performance on TSP problems may advance our understanding of human/animal cognition.

Our Contributions

We trained pigeons with increasing set sizes of up to six goals, with each set size presented in three distinct configurations, until consistency in route selection emerged. After training at each set size, the pigeons were tested with two novel configurations. All pigeons acquired routes that were significantly more efficient (i.e., shorter in length) than expected by chance selection of the goals. On average, the pigeons also selected routes that were more efficient than expected based on a local nearest-neighbor strategy and were as efficient as the average route generated by a crossing-avoidance strategy. Analysis of the routes taken indicated that they conformed to both a nearest-neighbour and a crossing-avoidance strategy significantly more often than expected by chance. Both the time taken to visit all goals and the actual distance traveled decreased from the first to the last trials of training in each set size. On the first trial with novel configurations, average efficiency was higher than chance but was not higher than expected from a nearest-neighbor or crossing-avoidance strategy. These results indicate that pigeons can learn to select efficient routes on a TSP problem.



Computational Models of Hiding and Seeking

Problem Formulation

Hiding and seeking are considered to be non-trivial human cognitive behaviors that develop with age. These behaviors are present in a variety of video games in some form. For instance, competitive on-line first-person shooters such as Counter-strike: Source have players searching for members of the opposing team (e.g., snipers). Role-playing games such as Borderlands or Fallout: New Vegas encourage the player to explore the environment and reward such exploration with weapons, side quests and information on the story and the environment.

To support these hide and seek activities, game developers face several challenges. First, level designers need to place desirable items (“loot”) in locations that would reward both casual and hardcore players. Deciding on which kinds of items to place at which locations can be made easier and more efficient by predicting, at the game development stage, where the players will search and how their search patterns will depend on the player type (e.g., from a casual player to a completionist). Second, game designers can enhance behavior of in-game artificial intelligence (AI) controlled agents with knowledge of where the players will be looking for other players (e.g., in Counter-strike: Source) or other player’s units (e.g., in StarCraft 2). This would allow the AI agents to better control the level of stealth they exhibit in the game. Finally, game developers need to develop non-playable characters that search for the player in a compelling way. A common approach is to give such characters a perfect knowledge of the player’s position and then add hard-coded behavior obfuscating such omniscience. Naturally looking obfuscation is labor-intensive as it requires extensive trial-and- error iterations and may be fragile insomuch as every once in a while the characters demonstrate their omniscient knowledge of player’s position. This is viewed as “cheating” in video games and can break player’s immersion.

Beyond video games, understanding hiding and seeking is valuable to law-enforcement agencies (e.g., predicting hiding spots for illegal substances) and the military (e.g., predicting locations of weapon stashes, improvised explosive devices, enemy troops or sniper positions). From a theoretical and cognitive perspective, if hiding and seeking are fundamental cognitive abilities of humans then understanding them via a computer program/model may shed light on human cognition and/or bring us closer to building strong Artificial Intelligence.

Our Contributions

We have studied human hide and seek behavior in real-world environments as well as their virtual reality counter-parts. In addition to statistical analysis of the collected data, we set out to build a predictive model of hide-and-seek behavior. To evaluate its fidelity we introduced a specialized version of the Turing test for hiding and seeking. We then developed a computer agent that passed the test by appearing indistinguishable from human behavior to a panel of human judges. We analyzed the Artificial Intelligence techniques that enabled the agent to imitate human hide and seek behavior and their relative contribution to the agent’s performance.



Computational Models of Emotion

Problem Formulation

There are several compelling reasons to study emotionally and culturally affected behavior. First, emotions and culture have a profound effect on most human behavior and, therefore, they should be modeled in any high-fidelity virtual human simulation. Second, emotions may play a fundamental role in human reasoning and cognition and, therefore, they should be given a serious consideration by scientists in Artificial Intelligence. Third, by modeling emotions of the trainee/player, intelligent systems and video games can be made more effective.

Our Contributions

We combined an existing computational model for culturally affected behavior (CAB) with a subset of an appraisal-based emotion model (EMA). The resulting model, Culture, EMotion and Adaptation (CEMA), is a light-weight computational engine capable of adding culturally and emotionally affected behaviors to non-playable characters in immersive training systems, with the aim of increasing their believability and, consequentially, their training effectiveness.