• Current Research
• Past Research
• Publications Directory

My research has largely focussed on trying to find approximation methods for solving otherwise intractable POMDPs. You can read my research statement to find out why I think this is scientifically interesting.

• E-PCA for POMDPs

  Standard value function approaches to finding policies for Partially Observable Markov Decision Processes (POMDPs) are intractable for large models. The intractability of these algorithms is due to a great extent to their generating an optimal policy over the entire belief space. However, in real POMDP problems most belief states are unlikely, and there is a structured, low-dimensional manifold of plausible beliefs embedded in the high-dimensional belief space.

  I have introduced a new method for solving large-scale POMDPs by taking advantage of belief space sparsity. The dimensionality of the belief space is reduced by exponential family Principal Components Analysis (Collins et al. 2001), which allows us to turn the sparse, high-dimensional belief space into a compact, low-dimensional representation in terms of learned features of the belief state. I then plan directly on the low-dimensional belief features. By planning in a low-dimensional space, I can find policies for POMDPs that are orders of magnitude larger than can be handled by conventional techniques.

  N. Roy and G. Gordon. ``Exponential Family PCA for Belief Compression in POMDPs''. Advances in Neural Information Processing (15) NIPS, Vancouver, BC. Dec. 2002. To appear.
  [Compressed postscript] [PDF]

• Nursebot

  Since the summer of 1999, I have been working on the Nursebot project, a research project joint with the University of Pittsburgh and the the University of Michigan. The goal of our project is to develop mobile, personal service robots that assist elderly people suffering from chronic disorders in their everyday life. We are currently developing an autonomous mobile robot that "lives" in a private home of a chronically ill elderly person. The robot provides a research platform to test out a range of ideas for assisting the elderly, such as intelligent reminding, tele-presence, data collection and social interaction. M. Montemerlo, J. Pineau, N. Roy, S. Thrun and V. Varma. ``Experiences with a Mobile Robotic Guide for the Elderly''. Proceedings of the International Conference on Artificial Intelligence (AAAI 2002). Edmonton, Jul. 2002 [Compressed postscript] [PDF] [BiBTeX Entry]

• Motion Planning

  I have published multiple papers on motion planning under positional uncertainty. Most recently, I proposed a motion planning algorithm for performing policy search in the full pose and velocity space of a mobile robot. By comparison, existing techniques optimize high-level plans, but fail to optimize the low-level motion controls. I use policy search in a high dimensional control space to find plans that lead to measurably better motion planning. The experimental results suggest that this approach leads to superior robot motion than many existing techniques.

  N. Roy and S. Thrun. ``Motion Planning through Policy Search''. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2002). Lausanne, Switzerland, Sept. 2002
  [Compressed postscript] [PDF] [BiBTeX Entry]

• Dialogue management

  Spoken dialogue managers have benefited from using stochastic planners such as Markov Decision Processes (MDPs). However, so far, MDPs do not handle well noisy and ambiguous speech utterances. We use a Partially Observable Markov Decision Process (POMDP)-style approach to generate dialogue strategies by inverting the notion of dialogue state; the state represents the user's intentions, rather than the system state. We demonstrate that under the same noisy conditions, a POMDP dialogue manager makes fewer mistakes than an MDP dialogue manager. Furthermore, as the quality of speech recognition degrades, the POMDP dialogue manager automatically adjusts the policy.

  N. Roy, J. Pineau & S. Thrun. ``Spoken Dialog Management for Robots''. Association for Computational Linguistics (ACL 2000). Hong Kong, Oct. 2000
  [Compressed postscript] [PDF] [BiBTeX Entry]

• Minerva

  In the summer of 1998, I was part of the Minerva team. Minerva was a robot that gave tours in the Smithsonian National Museum of American History. My part of the project involved making the navigation module more robust. The particular solution that I developed in conjunction with the rest of the Minerva team is Coastal Navigation -- a technique for increasing navigational robustness by overcoming lack of environmental structure and dynamic environments. More detail, images and papers on Coastal Navigation are available.

• Programming with Uncertainty

  For a couple of months, I worked on a formalism for developing robot behaviours using a combination of traditional programming methodologies and machine learning techniques. A position paper on this topic to the AAAI-98 Spring Symposium on Integrating Robotics Research is available here in pdf form. Sebastian now has a technical report on this topic.

• Odometric Error Parameter Estimation

  This work proposes a statistical method for calibrating mobile robots. In contrast to previous approaches, which require explicit measurements of actual motion when calibrating a robot, the algorithm uses the robot's sensors to automatically calibrate the robot as it operates.

  A copy of a paper on this work published at ICRA '99 is available.

• Multi-agent Robotic Exploration &Rendezvous

  We consider the problem of rendezvous between two robots exploring an unknown environment. That is, how can two autonomous exploring agents that cannot communicate with one another over long distances meet if they start exploring at different locations in an unknown environment. The intended application is collaborative map exploration.

  This work was my M.Sc thesis, performed at McGill University's Centre for Intelligent Machines, under the supervision of Dr. Gregory Dudek. Two papers on this work were published at the European Workshop on Learning Robots 1996 (EWLR-6) and at AAAI 97. A copy of the paper published at EWLR-6 is available.

• Surface Sensing and Classification for Efficient Mobile Robot Navigation

  A boom-mounted microphone is tapped on different floor materials, much as a blind man might tap his cane. The acoustic signature arising from the contact is then used to classify the floor type by comparing a windowed power spectrum of the acoustic signature with one of a family of prototypical signatures generated statistically from the same material. The technique is low-cost, involves limited computational expense, and performs very well. By sensing and then classifying the surface type, an estimate of the rate of error accumulation for dead-reckoning allows us to estimate accurately how often localization, including sensor data acquisition, must be performed.

  This work was performed at McGill University with Dr. G. Dudek, in collaboration with Dr. P. Freedman at the Centre de Recherche Informatique de Montréal, and published in Proc. IEEE/RSJ ICRA 1996. A copy of this paper is available.

• Other Projects

  While studying at McGill, I participated in the robot competitions at the AAAI National Conferences in 1996 and 1997 (my involvement in the 1997 was in a much reduced fashion. Two extended abstracts that the McGill Mobile Robot Lab published are available here: 1996 and 1997.

  I also spent some time developing a map description language, called GML. It has its failings (many!) and is stuck at that awkward age where it has too many features to be easy, but not enough to be powerful. If I ever get back to GML, it would be a useful addition to projects I have going now. For the curious, the man pages are here. I would recommend the curious wait for v 2.0, however.