Current Research Interests

My current research interests in Computer Science fall into the broad and interdisciplinary field of artificial intelligence (AI). This is concentrated in two areas: multi-agent systems, including hardware (robots) and software (agents), and robotics. Multi-agent systems is commonly considered to involve the development and deployment of groups of intelligent components that interact to deal with the world and solve complex problems beyond the capabilities of any single system, and adapt as those domains change. While this encompasses much of my work in this area, it is also much more multi-disciplinary than that definition might imply. Since it involves potentially interacting with agents that are self-interested, it involves much of economics and complex systems theory; since it involves interacting computer processes, it involves many elements of what are traditionally considered the "systems areas" of computer science, such as distributed computing; and since it may be embodied, it can involve much of robotics. Robotics itself is also strongly interdisciplinary, and involves intelligent control and computer vision, as well as areas more associated with engineering, such as electronics and mechanics.

I believe strongly that in order to advance the state of artificial intelligence, we must consider hard problems in real-world domains. Much of the work that he and I do, independently and collaboratively, involves dealing with problems that can be solved for specific instances in simple domains, but become extremely difficult to perform in general cases. Robotic control is an example of this: it is not difficult to write a controller to drive a mobile robot around on a flat surface with unvarying lighting and well-known obstacles. That same controller, however, will not function if the robot is placed on a gravel road in an unknown area under poor lighting conditions. While those working on such problems might commonly defer to specialized hardware or other assumptions about the domain (e.g. using a GPS receiver), those conditions remove the generality of the solution that is developed. I argue that advancing the state of AI requires less reliance on such specialized systems (e.g. humans have navigated successfully in their day-to-day activities without GPS for almost all of history, and most of us still do). The solutions produced without such assumptions are more generally applicable (e.g. a navigator would work deep in a mine, in a disaster area or military domain where GPS was jammed or disrupted, or on another planet). The techniques used in such solutions will also hopefully be adaptable to other problems requiring intelligent behaviour as well.

The typical domain that I consider in light of the work that I do is robotic rescue (often referred to as Urban Search and Rescue or USAR), where a group of robots would be expected to collaborate in a collapsed building or other disaster area, to produce a single map and search for human survivors. This brings about all of the challenges that a generally intelligent approach would require: the domain is highly uncertain, pre-specified maps would only be useful to a very limited degree, GPS and other forms of communication could be unavailable or restricted in range, and the major motivation for deploying robots is expendability in a dangerous setting. These characteristics are also true to some degree for a wide variety of security and surveillance domains, and should allow the solutions developed to be more applicable to the real world in general

The various areas below are some of my more specific interests within this realm. While I am attempting to overview these as individual topics, these projects are mainly part of one coherent whole: I wish to approach a domain with the challenging characteristics of the USAR domain described above, and allow a team of robots to collaboratively explore and produce a map of such a domain, in a collaborative manner and with minimal redundancy, leveraging off different skills each robot may possess (heterogeneity), and interacting with humans as necessary but able to function as autonomously as they are permitted. Ideally these robots would have little or no prior knowledge of the domain or low-level details of potential collaborators (e.g. where other robots were initially placed or even how many existed).

Much more information is available at our laboratory, including a library of publications. Most of my work in robotics is collaborative with Jacky Baltes, with whom I run our lab. If you're interested in any of this, by all means contact me.

Collaborative Multi-Agent Exploration in Complex Uncertain Environments

The exploration of an unknown complex and dynamic environment is a problem that is very naturally suited to the use of multiple intelligent agents. This problem encompasses numerous useful applications of artificial intelligence - Urban Search and Resue, as described above, and similar applications in security and information gathering, for example, but also many applications in mining, space exploration, and remote sensing as well. Most approaches to coordinating groups of mobile intelligent agents make assumptions that allow a team to perform this task in simple laboratory settings or in simulation, but fail in difficult, real-world environments. Some use a centralized controller in constant communication with agents, or restrict the activities of some or all agents, . Communication is also artificial, in that for one agent to tell another where it has been, the agent receiving the communication is provided with terms of reference (e.g. an absolute location in terms of some shared coordinate system as a grounding for landmarks). In a real world disaster rescue, such information would not be available - one agent perceiving a useful landmark would not allow everyone else in other places to know where it is - and communication would be unreliable at best. I am interested in developing and experimenting with methods for decentralized coordination in such environments. The intent is to allow a group of mobile robotic agents to explore a complex environment in as coordinated a fashion as possible while having no central controller. This is done by taking advantage of obvervations of the other agents, and selectively communicating information about the environment and other agents only when they physically encounter one another. To be able to communicate, agents must to note the appearance of useful landmarks in the environment, and make and interpret communications in terms of descriptions of these, as humans do, while also attempting to develop shared groundings for landmarks over time to improve communication. This involves work in a number of the areas listed below, and also much basic robotic research in areas such as localization, path planning, mapping, motor control, and perception. My work in this area has included contributions to our RoboCup, IJCAI, and AAAI robotic rescue teams.

I have also done much work related to similar coordination issues in domains other than USAR. In attempting to leverage the power of groups of agents to these types of problems, my students and I have exploited many different techniques, some of which we have also used in other environments. For example, weI have worked with stigmergy (marking locations in the environment) to greatly speed up the process of navigation in a complex, three-dimensional domain using purely reactive agents. This example involved software agents, and was implemented using the Half-Life game engine for experimentation purposes.

Mixed-Initiative Control of Robot Teams

Since the current state of the art in artificial intelligence and robotics does not allow completely autonomous systems to function well in domains such as USAR, the vast majority of deployed systems require teleoperation by humans. The difficulty with this is not just the requirement of human involvement and the limitation that has on the number of deployed systems, but that humans have a difficulty maintaining remote situational awareness and become fatigued and error-prone after just a short time. My students and I have been working with techniques for designing, building, and deploying Teleautonomous systems, where robots are as autonomous as possible within the setting in which they find themselves, requesting advice or control from a human operator as needed. This is an example of what is commonly called a mixed-initiative system, where intelligent agents and humans share control. The intent of this is to allow a larger group to be deployed given the same number of human operators, and to improve overall team performance. My students and I are currently working on extending this work to move from individuals appropriately contacting human operators to having them advice one another.

Grounded Communication in Multi-Agent Systems

Effective communication is generally a significant factor in improving the performance of a team. In order to be able to communicate, a group of agents must share a common context: a set of symbols and semantics, for example, or in the case of mobile robots, a common context for locations in the environment. For example, if a group of robots is mapping an area, in order to share and integrate partial maps these must be related to one another through common landmarks or a coordinate system. While GPS can supply the latter, its error factor can be affected strongly by construction materials, its signal can be jammed, and there are many interesting applications, such as mining or space exploration, in which it cannot exist. My students and I have been working on developing approaches to allow a group of robots or mobile agents to develop common groundings to support communication. Our methods focus on allowing individuals to do useful work while increasing the effectiveness of team communication. The overall goal is to allow a team of robots to be dispersed over a wide area, with no initial knowledge of the environment and no shared information, and allow them to learn a common framework for communication (through demonstration and local communication) as their own exploration work ensues. Our work focuses on local interactions only: we assume that communication will be sporadic and interrupted, and that it is impossible to broadcast successfully to the entire group. We are currently working on extending the techniques we have developed thus far to work with robots that are heterogeneous in ability - this greatly complicates this problem, since for example, one robot may designate a location based on a landmark that is not detectable to another robot.

Social Learning

While learning is commonly thought of as being based on taking input from a designated teacher or via reinforcement from the environment, there is a wealth of information that can be exploited by groups. On a human team, for example, reinforcement is commonly given from fellow players, or even by spectators, and we learn from such reinforcement every day. Similarly, much of what we do involves watching how others perform activities, and we leverage tremendous power in terms of improving our own performance by integrating the observations of others. Some of my work involves attempting to harness the information available in social settings to reflect what humans do every day. I have been working from two different perspectives in this regard. First, in social reinforcement learning, my students and I (and previous NSERC summer students) have worked on integrating reinforcement from teams, and working with the meta-level problem of judging to what degree an agent should attempt to learn from different particular individuals on a team. That is, an agent offering reinforcement may not in fact be very good at the skill in question itself, and so an agent must model the skills of others in conjunction with reinforcement learning in order to maximize the amount of potential information gain from a given team. This work also applies in modelling opponents or neutral third parties for similar purposes. The other major focus in the recent work of my students and I is imitation learning using Hidden Markov Models (HMMs), using global vision in a robotic soccer domain. This involves a learning robot viewing demonstrations of a particular task by other robots, in order to learn to perform that task well itself. There are challenges in this domain analogous to those in social reinforcement learning, in that a demonstration of a skill such as a soccer kick may not be done particularly well by some individuals, or may involve superfluous actions, and a learner must differentiate the performance of skilled agents from those that are less skilled, and learn elements of the skill appropriately. It must also be able to generalize, to deal with situations where one part of a demonstrated activity is done poorly and another done well, in order that demonstrations from a range of individuals that are imperfect can result in a complete skill being learned. This generalization is even more important in a robotic domain, since robots can be highly heterogeneous. A humanoid robot, for example, might step over an obstacle to get to a ball and kick it, whereas a wheeled robot would be forced to drive around the same obstacle, resulting in two very different visual demonstrations of the same activity.

Team and Coalition Formation

In most multi-agent systems research, a team (or the nature of the relationship between agents if the term "team" is not appropriate in the domain) is prespecified by the researcher. In recent years, the concept of how agents can form useful teams despite self-interest has arisen, both in order that agents can learn to form better teams than might be done by hand, and so that agents can be viewed more independently (e.g. two different groups might bring teams of robots to a disaster area and expect them to be able to form useful teams and cooperate immediately). My students and I have done a range of work in this area over the years, from recognizing the skills useful in teams (part of the reinforcement learning work described above) to deciding as a group when it is useful to exclude or include certain individuals. I am currently extending this work to deal with heterogeneous robots in the context of multi-agent exploration, by allowing agents to recognize when tasks are outside of their own abilities (e.g. a space is too small to enter), recruiting other agents (from a temporary instance to a long-term partnership) and allocating tasks to other they encounter. This is intended to allow a larger team to be dispersed in an exploration area than might otherwise be possible (i.e. divide funding to support a few very expensive but highly maneuverable robots and many more cheaper but more mobility-restricted units), and allow the group to distribute the necessary work dynamically and in a distributed fashion as they encounter one another (while taking advantage of any structuring that is provided beforehand, such as known authority relationships). While we have previously done work in coalition formation in mobile software agents, where the work involves issues such as deception in claims of ability vs. actual performance, or the amount an agent gives to the team as opposed to benefiting from the association, here there are important physical constraints provided by the mobile setting. If a limited-functionality robot agrees to work with a particular leader, for example, it is limited in its ability to others and must remain in a reasonable proximity to that leader in order to interact and communicate, which constrain its abilities. Similarly, a robot acting as a leader for such a robot may have to actively guide it, limiting the number of such entities it can divide its time between and constraining its ability to do useful individual work.

This type of work is becoming more important in conjunction with the development of a range of small, highly-mobile (and possibly reconfigurable) robots for security and surveillance purposes. While these are becoming smaller and more interesting every year, there are still strong limitations on the amount of local processing available to very small robots, necessitating partnerships with others that have these abilities (or off-line processing that may not be possible in a very remote environment).

Mixed-Reality Robotics

As mentioned above, one of the of the more exciting aspects as robotics research progresses involves working with increasingly miniaturized components. This requires work in adapting solutions that are designed for large robots on smaller, processing-limited, and error-prone devices such as the Citizen Microrobots (see images on my lab website). We are the only group in Canada currently working with these robots, which employ an ARM processor and can thus perform sophisticated local computation. Robots like these can be used as the limited-ability robot in the work described above, and because of their size, can also be used to perform a wide-range of multi-robot work in a small space. They also have the functionality to be used like any other wheeled robot that does not require local vision (we placed third in the world in the Microrobot events in RoboCup in 2007 using the first generation of these robots).

Jacky Baltes, my students, and I have been working on developing and enhancing a mixed reality environment for these robots. The robots themselves are small and light enough to run on the surface of a TV screen, on which can be projected any reality we wish. In playing soccer for example, the lines and even the ball can be virtually generated. For research purposes, this allows an ideal combination of the control provided by simulation and the physical grounding provided by real robots. In testing navigation and path planning algorithms, for example, we can place virtual obstacles that move with precise degrees of randomness and guarantee validity across trials. We have a number of papers describing this mixed reality approach and its use in education (including the application of video games to robotic education, as depicted in the right image above) and research. My students and I continue to improve both the approach itself and its application in these areas.

We are also using or are about to use these robots in much of the work described above: they are some of the demonstrators in imitation learning, some of the partners in team formation, and I will be using these for further work on navigation and path planning using adaptive robot formations, since these robots allow me to experiment with larger team sizes effectively in the laboratory.

Humanoid Robotics

In terms of challenges to intelligent control and potential for return, there are few better alternatives than work on the humanoid form. Humans interact more naturally with the humanoid form they are familiar with, and our world is already adapted to the humanoid form, making it advantageous for robots to be similarly embodied. The number of degrees of freedom is enormous, however, compared to the types of robots that are used with most of the work done in robotics research today. This adds a great deal of complexity even to problems that are considered to have common solutions in wheeled robots. For example, simultaneous localization and mapping (SLAM) for humanoids involves dealing with the huge range of error in the humanoid pose at any point, and the greater error in terms of estimating distance traveled (since steps are erratic over rough terrain) and perceiving the environment (since error from vision is also affected by the humanoid pose). The advantage, however, is obvious: humanoid robots can crawl, climb, and otherwise traverse areas that would be impossible for wheeled robots. Like our other robotic work, Jacky Baltes and I are working with using simple devices (e.g. humanoid kits from Japanese fighting robots designed to be teleoperated) with simple on-board devices (cell phones for vision and local computation) to tackle these problems. We are currently working on using the accelerometers in cellular phones to perform active balancing, as well as on intelligent control for complex motions, such as combinations of walking, crawling, and lifting. Humanoid robots are also used in other aspects of my work: they are some of the demonstrators in the imitation learning work described above, and will be used in future as some of the partners in the team formation work described above. I am the program chair for the 1st International Conference on Humanoid Robotics Research, to be held in Incheon, Korea, in August, 2009.

Earlier Research Interests

Prior to the work described here, I have done work in pragmatic user modelling, which manifests itself currently in an interest in human-robot interaction that comes into play with the teleautonomy work described above. I have also done work on adaptive planning and improvisation, which forms a basis for much of my current interest in complex robot motion planning that underlies much of the multi-robot interaction work described above, and work in simulation environments for intelligent agents. Papers related to this earlier work are also available on my lab website.

Should you wish to contact me, you can email andersj@cs.umanitoba.ca. For secure mail, my PGP public key is here.