We present algorithms for environment exploration in the context of a habitat monitoring task, where the goal is to track radio-tagged invasive fish with autonomous surface or ground robots. The first task is navigation around an unknown obstacle using an input from a front-facing sonar. This capability is important for navigation on inland lakes, because plants and shallow shorelines are hard to map in advance. The second task involves energy harvesting for long-term operation. We address the problem of exploring the solar map of the environment which is used for energy-efficient navigation. For both problems, we present online algorithms and examine their performance using competitive analysis. In competitive analysis, the performance of an online algorithm is compared against the optimal offline algorithm. For obstacle avoidance, the offline algorithm knows the shape of the obstacle. For solar exploration, the offline algorithm knows the geometry of the shadow-casting objects. We obtain an $O(1)$ competitive ratio for obstacle avoidance and an $O(\log n)$ competitive ratio for solar exploration, where $n$ is the number of critical points to observe. The strategies for obstacle avoidance are validated through extensive field experiments, and the strategies for exploration are validated with simulations.

This paper addresses a fundamental search problem in which a searcher subject to time and energy constraints tries to find a mobile target. The target's motion is modeled as a random walk on a discrete set of points on a line segment. At each time step, the target chooses one of the adjacent nodes at random and moves there. We study two detection models. In the no-crossing model, the searcher detects the target if it is on the same node or if it takes the same edge at the same time. In the crossing model, detection happens only if the target lands on the same node at the same time. For the no-crossing model, where move and stay actions may have different costs, we present an optimal search strategy under energy and time constraints. For the crossing model, we formulate the problem of designing an optimal strategy as a partially observable Markov decision process (POMDP) and solve it using methods that reduce the state-space representation of the belief. The POMDP solution reveals structural properties of the optimal solution. We use this structure to design an efficient strategy and analytically study its performance. Finally, we present preliminary experimental results to demonstrate the applicability of our model to our tracking system, which is used for finding radio-tagged invasive fish.

We study the lion-and-man game in which a group of lions (the pursuers) try to capture a man (the evader). The players have equal speed. They can observe each other at all times. While the game is well-studied in planar domains such as polygons, very little is known about its properties in higher dimensions. In this paper, we study the lion and man game when played on the surface of a genus-zero polyhedron with boundary. We show that three lions with non-zero capture distance δ can capture the man in time O((A/δ2+ L/δ)2δ/2) where A is the area of the surface, and L is the total edge length of the surface.

This paper studies the problem of searching for an unknown moving target in a bounded two-dimensional convex area with a mobile robot. A key component of designing a search strategy is the target motion model, which is often unknown in practical scenarios. When designing search strategies, researchers either (1) ignore the target motion and treat the target as a stationary object with unknown location, (2) treat the target as an adversary and model the search task as a game, or (3) use a stochastic model such as a random walk. For each of these models we analyze possible search paths with the objective of minimizing the expected capture time. Our intent is to investigate how the choice of the model influences the choice of the strategy and consequently how the capture time will depend on this choice. In addition to a theoretical analysis, we compare the strategies in simulation.

We present deterministic strategies for capturing a target performing a discrete random walk on a discretized line segment. The searcher has a limited time budget. Its goal is to maximize the probability of capturing the target within the budget. A challenging aspect of our model is that the target can cross the searcher without being captured when they take the same edge at the same time in opposite directions. We present a Partially Observable Markov Decision Process (POMDP) approach for finding the optimal search strategy. We also present an efficient approximate solution to the POMDP. The strategies found by this approach reveal structural properties of the efficient search strategies which we exploit to solve the problem efficiently without running the POMDP.

In this paper we study the problem of designing search strategies to find a target whose motion is described by a random walk along a one-dimensional bounded environment. The sensing model and the characteristic of the environment require the searcher and the target to be on the same site at the same time to guarantee capture. The objective is to optimize the searcher's motion, given by a sequence of actions (move right, left or remain stationary), so that the probability of capturing the target is maximized. Each action is associated with an energy cost. The searcher strategy is constrained by a total energy budget. We propose a class of randomized strategies for which we provide an analytical expression for the capture probability as a function of a single parameter. We then use this expression to find the best strategy within this class. In addition to theoretical results, the algorithms are analyzed in simulation and compared with other intuitive solutions.

In cognitive radio (CR) networks, the secondary users (SUs) try to communicate opportunistically in the frequency band originally allocated to a primary network. This communication should be in a manner that the quality of service (QoS) is satisfied for both primary and secondary networks. In this paper, the considered system consists of a primary broadcasting network with one transmitter and M receivers, and a relay-assisted secondary network with one transmitter and one receiver. In this scheme, if the direct link between the cognitive transmitter and receiver is not maintained the target signal to interference plus noise ratio (SINR), the relaying process, begins where N relays assist the transmitter to transmit its data to the receiver. This relaying process continues until the target SINR is met at the cognitive receiver. This scheme employs joint power allocation and beamforming (BF) at the relay nodes and defines two optimization problems in a way that the objective in the first problem is minimization of the total transmission power of the relays. If there is not any feasible solution for the first problem, the second problem is proposed with the objective of maximizing the receive rate at the destination node. Genetic algorithm (GA) is applied to both defined problems to find optimum transmission power values and beamforming weight in the relay nodes. Simulation results show that applying beamforming scheme results in a considerable reduction in the total transmission power of the relay nodes, while satisfying the QoS in both primary and secondary networks.

A cognitive radio (CR) network is a secondary network operating in the frequency band and geographical area of a primary network to which the spectrum is licensed. In this paper, we consider a primary broadcasting network consisting of a transmitter and a number of primary users (PUs). The secondary users (SUs) make opportunistic unlicensed spectrum access to communicate with their base station (BS). With this system model, a joint power allocation and beamforming scheme is proposed in the uplink of the CR network to minimize the maximum interference to the PUs in two different scenarios. In the first scenario, the primary transmitter does not cooperate with the CR network and it transmits with a fixed power, whereas it cooperates in the joint power allocation and beamforming scheme and adjusts its transmission power accordingly, in the second scenario. In the former case, our proposed joint power allocation and beamforming scheme finds the beamforming weights and transmission power values under quality of service (QoS) constraints of all SUs, taking into account their maximum transmission power constraints. In the latter case, the proposed scheme finds the beamforming weights of the BS and transmission powers of primary transmitter and SUs under their target signal-to-interference-plus-noise ratios (SINRs) and maximum power constraints. Our approach employs Genetic Algorithm (GA) to determine optimum transmission power values and beamforming weight vectors. Simulation results show the performance of the proposed scheme.