We study the symmetric rendezvous search problem in which two robots that are unaware of each other’s locations try to meet as quickly as possible. In the symmetric version of this problem, the robots are required to execute the same strategy. First, we present a symmetric rendezvous strategy for the robots that are initially placed on the open plane and analyze its competitive performance. We show that the competitive complexity of our strategy is O ( d / R ) where d is the initial distance between the robots and R is the communication radius. Second, we extend the symmetric rendezvous strategy for the open plane to unknown environments with polygonal obstacles. The extended strategy guarantees a complete coverage of the environment. We analyze the strategy for square, translating robots and show that the competitive ratio of the extended strategy is O ( d / D ) where D is the length of the sides of the robots. In obtaining this result, we also obtain an upper bound on covering arbitrary polygonal environments which may be of independent interest.

This paper describes design and results of a human-robot interaction study aimed at determining the extent to which affective robotic behavior can influence participants' compliance with a humanoid robot’s request in the context of a mock-up search-and-rescue setting. The results of the study argue for inclusion of affect into robotic systems, showing that nonverbal expressions of negative mood (nervousness) and fear by the robot improved the participants' compliance with its request to evacuate, causing them to respond earlier and faster.

The majority of existing approaches to mobile robot mapping assumes that the world is static, which is generally not justified in real-world applications. However, in many navigation tasks including trajectory planning, surveillance, and coverage, accurate maps are essential for the effective behavior of the robot.  In this paper we present a probabilistic grid-based approach for modeling changing environments. Our method represents both, the occupancy and its changes in the corresponding area where the dynamics are characterized by the state transition probabilities of a Hidden Markov Model. We apply an offline and an online technique to learn the parameters from observed data. The advantage of the online approach is that it can dynamically adapt the parameters and at the same time does not require storing the complete observation sequences.  Experimental results obtained with data acquired by real robots demonstrate that our model is well-suited for representing changing environments. Further results show that our technique can be used to substantially improve the effectiveness of path planning procedures.

Recent works on multi-agent sequential decision making using decentralized partially observable Markov decision processes have been concerned with interaction-oriented resolution techniques and provide promising results. These techniques take advantage of local interactions and coordination. In this paper, we propose an approach based on an interaction-oriented resolution of decentralized decision makers. To this end, distributed value functions (DVF) have been used by decoupling the multi-agent problem into a set of individual agent problems. However existing DVF techniques assume permanent and free communication between the agents. In this paper, we extend the DVF methodology to address full local observability, limited share of information and communication breaks. We apply our new DVF in a real-world application consisting of multi-robot exploration where each robot computes locally a strategy that minimizes the interactions between the robots and maximizes the space coverage of the team even under communication constraints. Our technique has been implemented and evaluated in simulation and in real-world scenarios during a robotic challenge for the exploration and mapping of an unknown environment. Experimental results from real-world scenarios and from the challenge are given where our system was vice-champion.

Sequential auctions can be used to provide solutions to the multi-robot task-allocation problem. In this paper we extend previous work on sequential auctions and propose an algorithm that clusters and auctions uninitiated task clusters repeatedly upon the completion of individual tasks. We demonstrate empirically that our algorithm results in lower overall team costs than other sequential auction algorithms that only assign tasks once.

The ability to use a mirror as an instrument for spatial reasoning enables an agent to make meaningful inferences about the positions of objects in space based on the appearance of their reflections in mirrors.  The model presented in this paper enables a robot to infer the perspective from which objects reflected in a mirror appear to be observed, allowing the robot to use this perspective as a virtual camera.  Prior work by our group presented an architecture through which a robot learns the spatial relationship between its body and visual sense, mimicking an early form of self-knowledge in which infants learn about their bodies and senses through their interactions with each other.  In this work, this self-knowledge is utilized in order to determine the mirror's perspective.  Witnessing the position of its end-effector in a mirror in several distinct poses, the robot determines a perspective that is consistent with these observations.  The system is evaluated by measuring how well the robot's predictions of its end-effector's position in 3D, relative to the robot's egocentric coordinate system, and in 2D, as projected onto it's cameras, match measurements of a marker tracked by its stereo vision system.  Reconstructions of the 3D position end-effector, as computed from the perspective of the mirror, are found to agree with the forward kinematic model within a mean of 31.55mm.  When observed directly by the robot's cameras, reconstructions agree within 5.12mm.  Predictions of the 2D position of the end-effector in the visual field agree with visual measurements within a mean of 18.47 pixels, when observed in the mirror, or 5.66 pixels, when observed directly by the robot's cameras.

A popular approach to high dimensional control problems in robotics uses a library of candidate “maneuvers” or “trajectories”. The library is either evaluated on a fixed number of candidate choices at runtime (e.g. path set selection for planning) or by iterating through a sequence of feasible choices until success is achieved (e.g. grasp selection). The performance of the library relies heavily on the content and order of the sequence of candidates. We propose a provably efficient method to optimize such libraries, leveraging recent advances in optimizing submodular functions of sequences. This approach is demonstrated on two important problems: mobile robot navigation and manipulator grasp set selection. In the first case, performance can be improved by choosing a subset of candidates which optimizes the metric under consideration (cost of traversal). In the second case, performance can be optimized by minimizing the depth in the list that is searched before a successful candidate is found. Our method can be used in both on-line and batch settings with provable performance guarantees, and can be run in an anytime manner to handle real-time constraints.

We study a two-player pursuit-evasion game, in which an agent moving amongst obstacles is to be maintained within ``sight" of a pursuing robot. Using a discretization of the environment, our main contribution is to design an efficient algorithm that decides, given initial positions of both pursuer and evader, if the evader can take any moving strategy to go out of sight of the pursuer at any time instant. If that happens, we say that the evader wins the game. We analyze the algorithm, present several optimizations and show results for different environments. For situations where the evader cannot win, we compute, in addition, a pursuit strategy that keeps the evader within sight, for every strategy the evader can take. Finally, if it is determined that the evader wins, we compute its optimal escape trajectory and the corresponding optimal pursuit trajectory.

The Dempster-Shafer theory of belief functions is an important approach to deal with uncertainty in AI.In the theory, belief functions are defined on Boolean algebras of events. In many applications of belief functions in real world problems, however, the objects that we manipulateis no more a Boolean algebra but a distributive lattice. In this paper, we extend the Dempster-Shafer theory to the setting of distributive lattices, which has a mathematical theory as attractive as in that of Boolean algebras.Moreover, we apply this more general theory to a simple epistemic logic the first-degree-entailment fragment of relevance logic R , provide a sound and complete axiomatization for reasoning about belief functions for this logic and show that the complexity of the satisfiability problem of a belief formula with respect to the class of the corresponding Dempster-Shafer structures is NP-complete.

Knowledge compilation is a powerful technique for compactly representing and efficiently reasoning about logical knowledge bases. It has been successfully applied to numerous problems in artificial intelligence, such as probabilistic inference and conformant planning. Conditioning, which updates a knowledge base with observed truth values for some propositions, is one of the fundamental operations employed for reasoning. In the propositional setting, conditioning can be efficiently applied in all cases. Recently, people have explored compilation for first-order knowledge bases. The majority of this work has centered around using first-order d-DNNF circuits as the target compilation language. However, conditioning has not been studied in this setting. This paper explores how to condition a first-order d-DNNF circuit. We show that it is possible to efficiently condition these circuits on unary relations. However, we prove that conditioning on higher arity relations is #P-hard. We study the implications of these findings on the application of performing lifted inference for first-order probabilistic models.This leads to a better understanding of which types of queries lifted inference can address.