Hindawi Publishing CorporationEURASIP Journal on Advances in Signal ProcessingVolume 2009, Article ID 284525, 17 pagesdoi:10.1155/2009/284525Research ArticlePrioritized Multihypothesis Tracking bya Robot with Limited SensingPaul E. Rybski and Manuela M. VelosoSchool of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USACorrespondence should be addressed to Paul E. Rybski, [email protected] 1 August 2008; Accepted 1 December 2008Recommended by Matthijs SpaanTo act intelligently in dynamic environments, mobile robots must estimate object positions using information obtained from avariety of sources. We formally describe the problem of estimating the state of objects where a robot can only task its sensors toview one object at a time. We contribute an object tracking method that generates and maintains multiple hypotheses consisting ofprobabilistic state estimates that are generated by the individual information sources. These different hypotheses can be generatedby the robot’s own prediction model and by communicating robot team members. The multiple hypotheses are often spatiallydisjoint and cannot simultaneously be verified by the robot’s limited sensors. Instead, the robot must decide towards whichhypothesis its sensors should be tasked by evaluating each hypothesis on its likelihood of containing the object. Our contributedalgorithm prioritizes the different hypotheses, according to rankings set by the expected uncertainty in the object’s motion model,as well as the uncertainties in the sources of information used to track their positions. We describe the algorithm in detail andshow extensive empirical results in simulation as well as experiments on actual robots that demonstrate the effectiveness of ourapproach.Copyright © 2009 P. E. Rybski and M. M. Veloso. This is an open access article distributed under the Creative CommonsAttribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work isproperly cited.1. IntroductionRobot perception processing consists of a mapping fromsensory data to an estimate of the state of the elementsof the environment that are of relevance to the task underexecution. For example, a robot traversing a maze needsto estimate the area and position of open space and wallsfrom its sensory data. Similarly in a team of soccer robots,each robot has the potential to estimate the state of theenvironment based on its own sensing and on the infor-mation communicated by its teammates. The complexity ofstate estimation greatly increases with the task, the dynamicsof the environment, and the sensing capabilities of therobots.In our work, we consider that robots have limitedsensing and operate in complex and dynamic environmentsexecuting tasks that rely on multiple elements. We investigaterobot state estimation as a result of the integration of sensoryinformation obtained from a variety of sources, namely, therobot’s own sensors and actions, models and communicatedinformation from teammate robots’ sensors and actuators, aswell as models of the dynamics of the environment.Concretely, we investigate the problem when robots havelimited and narrow perceptual scope, such that they areonly capable of observing a single object (or a reduced setof objects) at a time with their sensors. Thus, the relativesize of the robot’s sensor scope is small compared to theenvironment, and while the state of a single object is beingupdated by the sensors, the evolving state of all othernonsensed objects must be predicted from communicatedinformation or from models learned from observations orprovided a priori.In addition to the complexity of the problem, not allsources of information about a single object can and shouldbe handled equally, as in the traditional sense of weightingthose estimates by their covariance. There are times whenempirical evidence has proven that some modalities mustbe ignored as they are unreliable in certain circumstances.2 EURASIP Journal on Advances in Signal ProcessingAdditionally, nondeterministic effects of actuators can createseveral distinctly different potential outcomes, each of whichmust be tracked and reasoned about separately.To address this challenge, we define a method forreasoning over a disjoint hypothesis space whereby high-level domain knowledge is used to impose a strict orderingon estimates created by different sources of information.By segmenting the sources of information used to reasonabout the state of environmental quantities into differentclasses, each with different state dynamics and expected effectof robot actions, a prioritized hierarchy of state estimatescan be inferred. Additionally, when tracking multiple objectssimultaneously, the evolving states of those objects must beconsidered carefully when deciding where to task the robot’ssensors.We describe a hybrid state estimation algorithm thatattempts to reduce the complexity of the generated probabil-ity density functions over a quantity of interest by factoringthe problem into a series of small estimation problems thatare tied to the different sources of model world informationpossessed by the robot. A high-level policy is used todetermine where to task the robot’s sensors to best trackthe objects in the environment. Such policies for creatinghierarchies can be defined a priori, or they could potentiallybe learned from data. Using this policy, the decision processthat governs each individual robot’s actions can easily selectthe most informative state estimate to use as its input. Thepriorities are set by the expected uncertainty in the object’smotion model as well as the uncertainties in the sources ofinformation used to track their positions. Robot’s actionsdirectly affect its perception of the environment as well asthe environment itself, and the best estimate is often onethat will allow the robot to obtain more information aboutits surroundings to further clarify its estimate of quantitiesof interest. This, in turn, provides more information to therobot that further updates the ordered hierarchy of possibleestimates.This paper describes an active state estimation algorithm,as applied to a real-time adversarial multirobot domain,which combines action policies determined from high-level domain knowledge with multimodal probabilistic stateestimators. In this work, we assume that each of the objectsthat are detected and tracked have unique sensor
View Full Document
Unlocking...