Computational Models of Human and Animal Cognition
Traveling Sales Pigeons
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.
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.
- Danielle M. Baron and Alejandro J. Ramirez and Vadim Bulitko and Christopher R. Madan and Ariel Greiner and Peter L. Hurd and Marcia L. Spetch. Practice Makes Proficient: Pigeons (Columba livia) Learn Efficient Routes on Full-circuit Navigational Traveling Salesperson Problems. Animal Cognition. Pages 30. The final publication is available at Springer via http://link.springer.com/article/10.1007/s10071-014-0776-6
Computational Models of Hiding and Seeking
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.
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.
- Andrew Cenkner and Vadim Bulitko and Marcia Spetch and Eric Legge and Craig Anderson and Matthew Brown. 2013. Passing a Hide and Seek Third-Person Turing Test. IEEE Transactions on Computational Intelligence and AI in Games. PP(99). Pages 13. doi: 10.1109/TCIAIG.2013.2275162.
- Eric L.G. Legge and Marcia L. Spetch and Andrew Cenkner and Vadim Bulitko and Craig Anderson and Matthew Brown and Donald Heth. 2012. Not All Locations Are Created Equal: Exploring How Adults Hide and Search for Objects. PLoS ONE 7(5): e36993. doi:10.1371/journal.pone.0036993.
- Andrew Cenkner and Vadim Bulitko and Marcia Spetch. 2011. A Generative Computational Model for Human Hide and Seek Behavior. In Proceedings of the Seventh AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), pages 128-133. Stanford, California.
- Katherine J. Talbot and Eric L.G. Legge and Vadim Bulitko and Marcia L. Spetch. 2009. Hiding and Searching Strategies of Adult Humans in a Virtual and a Real-Space Room. Learning and Motivation. Volume 40, issue 2 (May), pages 221-233. Elsevier. The final version is here.
Computational Models of Emotion
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.
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.
Work in Progress
We are currently working on adding an appraisal-based emotion model to PAST which will allow its experience manager to accommodate the player's actions specifically to keep the player on an author-specified emotional trajectory. Our testbed for this project is iGiselle --- an interactive version of the Romantic ballet Giselle.
We are also developing a light-weight model of emotions compelling for inclusion in video games. In doing so we combine our previously developed appraisal-style model (CEMA) with recent work on resource-based models of emotions (e.g., COR-E).
- Sergio Poo Hernandez and Vadim Bulitko and Marcia Spetch. Keeping the Player on an Emotional Trajectory in Interactive Storytelling. In Proceedings of the Eleventh AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE). 2015.
- Yathirajan Brammadesam Manavalan and Vadim Bulitko and Marcia Spetch. A Lightweight Algorithm for Procedural Generation of Emotionally Affected Behavior and Appearance. In Proceedings of the Eleventh AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE). 2015.
- Yathirajan Brammadesam Manavalan and Vadim Bulitko. Appraisal of Emotions from Resources. In Proceedings of the Seventh International Conference on Interactive Digital Storytelling (ICIDS). 2014.
- Sergio Poo Hernandez and Vadim Bulitko and Emilie St.Hilaire. Emotion-based Interactive Storytelling with Artificial Intelligence. In Proceedings of the Tenth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE). 2014.
- Sarah Beck and Vadim Bulitko and Sergio Poo Hernandez and Emilie St.Hilaire and Nora Stovel and Laura Sydora. 2014. Women with Wings: The Romantic Ballerina Then and Now. Abstract in Proceedings of Grace Hopper Conference. Phoenix, Arizona. 2014.
- Sergio Poo Hernandez and Vadim Bulitko. A Call for Emotion Modeling in Interactive Storytelling. In the Proceedings of the Intelligent Narrative Technologies (INT) workshop of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE). Boston, MA. 2013.
- Vadim Bulitko and Steven Solomon and Jonathan Gratch and Michael van Lent. Modeling Culturally and Emotionally Affected Behavior. In Proceedings of the Artificial Intelligence and Interactive Digital Entertainment conference (AIIDE), pages 10 - 15. Stanford, California. 2008.
- Interactive Storytelling for Fun and Training. Invited talk at CogSem, Department of Psychology. University of Alberta. Edmonton, Alberta. September 12, 2014.
- Modeling Culturally and Emotionally Affected Behavior. The fourth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment. Stanford, California. October 22, 2008.