Modeling human activity using laser range-finders

The goal of this research was to detect and mathematically model activity and interaction patterns between humans. We recorded tracks of people in a variety of environments, such as offices, corridors, and courtyards using laser range-finders (identities of people are not detected). Activities include conversations, working at a desk, moving between doors and desks, following in corridors, and playing ping-pong.

I developed a method for representing spatial activity as a probability distribution over the space of possible displacements. I then used an entropy-based method for automatically segmenting a track of positions into sub-sequences each representing a distinct activity. The distinct activities are classified using hierarchical clustering into activity classes. These classes form the states of a Markov model which then becomes a high-level representation of the pattern of spatial behavior in that particular environment [1].

I also detected anomalous behavior where an anomaly is defined as an activity which occurs with a frequency significantly different from what is usually observed. We modeled the time behavior of activity as a Poisson process. This enabled us to compute the expected probability of seeing a particular number of such activities over a given time period and to flag an anomaly if this probability fell below a threshold [2].

Left to right: Two people playing ping-pong; the corresponding laser range-finder scans; Segmenting a player's motion track. Videos of these steps are at the project web page.

This work was carried out at the Robotics Research Lab of Prof. Maja Mataric and Prof. Gaurav Sukhatme. Here is the project web page.

References

[1] A. Panangadan , M. Mataric and G. Sukhatme, "Detecting anomalous human interactions using laser range-finders". In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), IEEE Press, pp. 2136-2141, 2004. (Details)

[2] A. Panangadan , M. Mataric and G. Sukhatme, "Identifying human interactions in indoor environments". In Proceedings of the Third International Joint Conference on Autonomous Agents and Multi-Agent Systems, IEEE Computer Society, pp. 1308-1309, 2004. (Details)

Embedding reasoning into a Sony Aibo robot

The goal of this project was to demonstrate that reasoning algorithms based on propositional logic could be executed even on low-power computer platforms if recent developments in the efficient representation of Boolean propositions are used. We used a Sony Aibo robot to demonstrate the embedded reasoning. We chose the grid-shaped Wumpus world described in Russell and Norvig's (1995) textbook as our problem domain. The plan to solve the Wumpus world problem is computed offline and stored as an Ordered Binary Decision Diagram (OBDD) in the robot's memory. The robot uses its vision system to identify its location in the grid world and then instantiates the appropriate variables in the OBDD. The instantiated action variable determines the direction in which the robot is to move. The project also involved writing vision and robot localization code, and programming for the real-time operating system on the Aibo.

Aibo in the Wumpus world

This work was performed with Prof. Adnan Darwiche at the UCLA Computer Science Department.

Russell, S.J. and Norvig, P. 1995 Artificial Intelligence: A Modern Approach, Prentice Hall, Englewood Cliffs, New Jersey.

Construction using autonomous agents in a simulated environment

My dissertation research demonstrated how agents equipped with a connectionist architecture could construct arbitrary physical structures in a simulated environment [1]. The goal was to build a group of autonomous agents that could together construct arbitrary structures in their simulated 2-dimensional environment. In addition, the agents should be able to learn the construction sequence itself, learn to exploit spatial and temporal correlations in the environment, and complete the construction task in an efficient manner. These objectives were achieved by coupling a behavior-based architecture with spatial maps and a connectionist action selection mechanism to facilitate learning. All objects in the environment (programmed using Java) are colored discs. Agents can move in their environment and sense discs located around them through distance sensors. An agent can also pick up a discs close to it and drop this disc at another location. Construction in this environment involves a group of agents picking up discs, and then dropping them at incomplete parts of the structure to be built. Agents also have to periodically "eat" and "drink" by moving toward food and water discs.

The agents have a behavior-based architecture with connectionist action selection. An agent has both reactive behaviors which are used primarily for "eating" and "drinking" and navigational planning behaviors that are used for construction tasks. The navigational planning behaviors use an egocentric grid-based representation of the world. Communication between agents can be used to reduce the effect of random sensory and odometry errors on the accuracy of the spatial maps. Path planning is implemented by spreading activation on sets of these grid-based maps. The shape of the structure to be built is also encoded on a grid in the form of a "bird's eye" view. Construction sites are determined by matching the grids representing the current state of the world with the desired "bird's eye" view.

Screenshot showing the construction environment

Architecture of an agent showing both reactive and navigational planning behaviors

The connectionist action selection mechanism makes different kinds of learning possible. An agent can learn the sequence of construction behaviors by imitating a teacher agent that is already programmed with this behavior sequence [2]. An agent can exploit any spatial and temporal regularities in the environment by reinforcing its reactive behaviors using Hebbian learning [3]. Each agent monitors its progress to detect deadlocks arising from interactions with other agents and uses unsupervised learning to change its behavior so that the deadlock is broken. This type of learning also leads to emergent behavior such as forming bucket brigades to transport material [4].

Example of spatial correlations

Example of temporal correlations

The order in which parts of the structure are built affects the completion time of the construction task. For instance, a brick dropped at a construction site can obstruct the paths of other agents. In certain cases, it might become impossible to complete the construction task if bricks are placed in a certain order. For instance, if the structure to be built is in the shape of two concentric circles. If the outer circle is completed before the inner one, then it becomes impossible for agents to reach the inner construction sites. I designed an algorithm that works by spreading activation over the spatial maps to determine the order in which discs are to be picked up in order to reduce the time taken to complete construction [5,6].

Spreading activations to match disc locations to drop-sites

This dissertation research was carried out under the supervision of Prof. Michael G. Dyer at the UCLA Computer Science Department.

References

[1] A. Panangadan, "Construction using autonomous agents in a simulated environment". Ph.D. Thesis, University of California, Los Angeles, 2002 [ps.gz]

[2] G. Chao, A. Panangadan and M. G. Dyer, "Learning to integrate reactive and planning behaviors for construction". In From Animals to Animats 6: Proceedings of the 6th International Conference on Simulation of Adaptive Behavior, Bradford Book/MIT Press, pp. 167-176, 2000. [ ps.gz, PDF ]

[3] A. Panangadan and M.G. Dyer, "Learning spatial and temporal correlation for navigation in a 2-dimensional continuous world". In Proceedings of the 19th International Conference on Machine Learning (ICML), Morgan Kaufmann, pp. 474-481, 2002. [ PDF ]

[4] A. Panangadan and M. G. Dyer, "Learning social behaviors without sensing". In From Animals to Animats 7: Proceedings of the 7th International Conference on Simulation of Adaptive Behavior, Bradford Book/MIT Press, pp. 387-388, 2002. [ ps.gz, PDF ]
(an expanded version of this poster is in the dissertation)

[5] Anand Panangadan and M. G. Dyer. "Goal sequencing for construction agents in a simulated environment". In Proceedings of the International Conference on Artificial Neural Networks (ICANN), Springer, pp. 969-974, 2002. [ ps.gz, PDF ]

[6] A. Panangadan and M. G. Dyer, "Construction by autonomous agents in a simulated environment". In Proceedings of the International Conference On Artificial Neural Networks (ICANN), Springer, pp. 963-970, 2001. [ ps.gz, PDF ]

Maze Navigation using Kohonen Self Organizing Maps

I used Kohonen Self Organizing Maps (SOMs) to build a navigation system for an agent in a maze. The agent first learns the layout of the maze and stores it in a SOM. Activation is then spread on the nodes of the SOM to enable the agent to find its way from any position in the maze to a goal location.

Nodes of the Kohonen self-organizing map representing a maze (after 10000 iterations)