A token is hidden in one of several boxes and then the boxes are locked. The probability of placing the token in each of the boxes is known. A searcher is looking for the token by unlocking boxes where each box is associated with an unlocking cost. The searcher conducts its search in rounds and must find the token in a predetermined number of rounds. In each round, the searcher may unlock any set of locked boxes concurrently. The optimization goal is to minimize the expected cost of unlocking boxes until the token is found. The motivation and main application of this game is the task of paging a mobile user (token) who is roaming in a zone of cells (boxes) in a cellular network system. Here, the unlocking costs reflect cell congestions and the placing probabilities represent the likelihood of the user residing in particular cells. Another application is the task of finding some data (token) that may be known to one of the sensors (boxes) of a sensor network. Here, the unlocking costs reflect the energy consumption of querying sensors and the placing probabilities represent the likelihood of the data being found in particular sensors. In general, we call mobile data any entity that has to be searched for.

This paper presents a novel method to construct a complete 3D map that includes all surfaces (ceiling, wall, and furniture tops, etc.) in indoor environments. A team of four robots, including three ground robots and one wall-climbing robot is deployed in a tetrahedron configuration that satisfies the perspective three point (P3P) problem. P3P problem is to estimate the pose of a perspective camera on the wall-climbing robot viewing three ground robots, which will produce up to four solutions using Grunert's algorithm while only one of them is genuine. We propose a probabilistic Bayesian algorithm that identifies the unique solution of the P3P problem using the mobility of the camera. Based on this technique, we introduce an intra-robot localization method to determine the geometric relationship among four robots. Each ground robot is equipped with a rotary laser range finder (LRF), a pan-tilt-zoom camera, and a LED cluster. The wall-climbing robot is fitted with a LRF, a perspective camera, and a motion sensor. Through the vision sensors, the robots obtain their relative poses by solving the P3P problem. Through the LRF on each robot, 4 laser point cloud maps are produced from each robot's point of view. With the information of relative poses of the multiple robots and the calibration data of each LRF and camera pair, the 4 partial maps are fused to acquire a complete 3D map that is rich with information of all surfaces. Our approach outperforms the traditional range image fusion algorithms in terms of time complexity and is suitable for real-time implementation. Real experiments verified the effectiveness of the method.

A mobile user is roaming in a zone composed of N cells in a cellular network system. When a call to the mobile user arrives, the system pages the mobile user in these cells since it never reports its location unless it leaves the zone. The N cells are associated with a probability vector (p1, ...,pN) where piis the probability that the mobile user resides in the ith cell and all the probabilities are independent. A delay constraint paging strategy must find the mobile user within D (1 les D les N) paging rounds; in each round a subset of the N cells is paged. The goal is to minimize the expected number of paged cells until the mobile user is found. Solutions based on dynamic programming that yield optimal strategies are known. The running time of the known implementations is Theta(N2D). Our first contribution is to improve the running time to Theta(ND) by proving that the dynamic programming recursive formulation satisfies the Monge property, permitting us to use various dynamic programming speedup techniques. A Theta(N) heuristic solution is also known. Our second contribution is a heuristic whose running time is Theta(N log D). Our heuristic outperforms the known heuristic while running faster for D << N. We compare the non-optimal heuristics with the optimal solution demonstrating the tradeoff between optimality and running time efficiency of various solutions.

This paper presents a new approach to the intralocalization among a team of robots working in constrained 3D space of urban environments. As the base formation, a team of three ground robots and one wall-climbing robot are deployed on ground and on a wall or ceiling, respectively. The three ground robots localize themselves using an existing panoramic vision-based method. However, no existing method can uniquely determine the pose of the climbing robot based on the positions of three ground robots in its image and in the world coordinate systems; up to four valid solutions could exist using known algorithms, although only one is genuine. By carefully examining these methods, two new algorithms for uniquely locating the climbing robot are proposed. The first algorithm makes use of the straight line constraint of robot motion and can uniquely determine the pose of climbing robot by moving the climbing robot straightly for two small steps. The second algorithm is based on the principle of Bayesian filter and take advantage of the motion sensor readings to loose the straight line constraint. The algorithm could continuously determine the climbing robot’s pose after the initial pose is obtained. Extensive simulations are conducted to validate the soundness and robustness of our algorithms. Preliminary experiments are also carried out to examine the feasibility in applying these algorithms in real robot applications.

This paper presents a self-localization strategy for a team of heterogeneous mobile robots including ground mobile robots of various sizes and wall-climbing robots. These robots are equipped with various visual sensors, such as miniature webcams, omnidirectional cameras, and PTZ cameras. As the core of this work, a formation of four-robot team is constructed to operate in a 3D space, e.g., moving on ground, climbing on walls and clinging to ceilings. The four robots could dynamically localize themselves asynchronously by employing cooperative vision techniques. Three of them on the ground mutually view each other and determine their relative poses with 6 degrees of freedom (DOFs). A wall-climbing robot, which significantly extends the work space of the robot team to 3D, is at a vantage point (e.g., on the ceiling) such that it can see all the three teammates, thus determining its own location and orientation. The four-robot formation theory and algorithms are presented, and experimental results with both simulated and real image data are provided to demonstrate the feasibility of this formation. Two 3D localization and control strategies are designed for applications such as search and rescue and surveillance in 3D urban environments where robots must be deployed in a full 3D space