Search

3D spatial perception is the problem of building and maintaining an actionable and persistent representation of the environment in real-time using sensor data and prior knowledge. Despite the fast-paced progress in robot perception, most existing methods either build purely geometric maps (as in traditional SLAM) or "flat" metric-semantic maps that do not scale to large environments or large dictionaries of semantic labels. The first part of this paper is concerned with representations: we show that scalable representations for spatial perception need to be hierarchical in nature. Hierarchical representations are efficient to store, and lead to layered graphs with small treewidth, which enable provably efficient inference. We then introduce an example of hierarchical representation for indoor environments, namely a 3D scene graph, and discuss its structure and properties. The second part of the paper focuses on algorithms to incrementally construct a 3D scene graph as the robot explores the environment. Our algorithms combine 3D geometry (e.g., to cluster the free space into a graph of places), topology (to cluster the places into rooms), and geometric deep learning (e.g., to classify the type of rooms the robot is moving across). The third part of the paper focuses on algorithms to maintain and correct 3D scene graphs during long-term operation. We propose hierarchical descriptors for loop closure detection and describe how to correct a scene graph in response to loop closures, by solving a 3D scene graph optimization problem. We conclude the paper by combining the proposed perception algorithms into Hydra, a real-time spatial perception system that builds a 3D scene graph from visual-inertial data in real-time. We showcase Hydra's performance in photo-realistic simulations and real data collected by a Clearpath Jackal robots and a Unitree A1 robot. We release an open-source implementation of Hydra at https://github.com/MIT-SPARK/Hydra. [ABSTRACT FROM AUTHOR]

We consider an ${m}$ server system in which each server can service at most one update packet at a time. The system designer controls (1) scheduling - the order in which the packets get serviced, (2) routing - the server that an arriving update packet joins for service, and (3) the service time distribution with fixed service rate. Given a fixed update generation process, we prove a strong age-delay and age-delay variance tradeoff, wherein, as the average AoI approaches its minimum, the packet delay and its variance approach infinity. In order to prove this result, we consider two special cases of the $m$ server system, namely, a single server system with last come first served with preemptive service and an infinite server system. In both these cases, we derive sufficient conditions to show that three heavy tailed service time distributions, namely Pareto, log-normal, and Weibull, asymptotically minimize the average AoI as their tail gets heavier, and establish the age-delay tradeoff results. We provide an intuitive explanation as to why such a seemingly counter intuitive age-delay tradeoff is natural, and that it should exist in many systems. [ABSTRACT FROM AUTHOR]

Futuristic communication network formed by autonomously operated, unmanned aerial vehicles, has piqued researchers interests in highly mobile wireless networks. Exchanging safety critical information, with low latency and high throughput, in such systems is of paramount importance. We study the broadcast capacity and minimum delay scaling laws for such highly mobile wireless networks, in which each node has to disseminate packets to all other nodes in the network. In particular, we consider a cell partitioned network under an IID mobility model, in which each node chooses a new position at random, every time slot. We derive scaling laws for broadcast capacity and minimum delay as a function of the network size. We propose a simple first-come-first-serve flooding scheme, which nearly achieve both capacity and minimum delay scaling. Thus, in contrast to what has been speculated in the literature, we show that there is nearly no tradeoff between capacity and delay. Our results also show that high mobility does not improve broadcast capacity. Our analysis makes use of the theory of Markov Evolving Graphs (MEGs), and develops two new bounds on flooding time in MEGs by relaxing the previously required expander property assumption. Simulation results verify our analysis, and throw up interesting open problems. [ABSTRACT FROM AUTHOR]

Age of information (AoI), defined as the time that elapsed since the last received update was generated, is a newly proposed metric to measure the timeliness of information updates in a network. We consider AoI minimization problem for a network with general interference constraints, and time varying channels. We propose two policies, namely, virtual-queue based policy and age-based policy when the channel state is available to the network scheduler at each time step. We prove that the virtual-queue based policy is nearly optimal, up to a constant additive factor, and the age-based policy is at-most a factor of 4 away from optimality. Comparison with previous work, which derived age optimal policies when channel state information is not available to the scheduler, demonstrates significant improvement in age due to the availability of channel state information. Our analysis relies on the age conservation law and age-square conservation law developed in this paper, which hold more generally and may be of independent interest. [ABSTRACT FROM AUTHOR]

Age of information (AoI) is a recently proposed metric for measuring information freshness. AoI measures the time that elapsed since the last received update was generated. We consider the problem of minimizing average and peak AoI in a wireless networks, consisting of a set of source-destination links, under general interference constraints. When fresh information is always available for transmission, we show that a stationary scheduling policy is peak age optimal. We also prove that this policy achieves average age that is within a factor of two of the optimal average age. In the case where fresh information is not always available, and packet/information generation rate has to be controlled along with scheduling links for transmission, we prove an important separation principle: the optimal scheduling policy can be designed assuming fresh information, and independently, the packet generation rate control can be done by ignoring interference. Peak and average AoI for discrete time G/Ber/1 queue is analyzed for the first time, which may be of independent interest. [ABSTRACT FROM AUTHOR]

We consider strategic arrivals to a FCFS service system that starts service at a fixed time and has to serve a fixed number of customers, for example, an airplane boarding system. Arriving early induces a higher waiting cost (waiting before service begins) while arriving late induces a cost because earlier arrivals take the better seats. We first consider arrivals of heterogenous customers that choose arrival times to minimize the weighted sum of waiting cost and cost due to expected number of predecessors. We characterize the unique Nash equilibria for this system. Next, we consider a system offering L levels of priority service with a FCFS queue for each priority level. Higher priorities are charged higher admission prices. Customers make two choices—time of arrival and priority of service. We show that the Nash equilibrium corresponds to the customer types being divided into L intervals and customers belonging to each interval choosing the same priority level. We further analyze the net revenue to the server and consider revenue maximizing strategies—number of priority levels and pricing. Numerical results show that with only a small number of queues (two or three) the server can obtain nearly the maximum revenue. [ABSTRACT FROM AUTHOR]

The distributed, low-feedback, timer scheme is used in several wireless systems to select the best node from the available nodes. In it, each node sets a timer as a function of a local preference number called a metric, and transmits a packet when its timer expires. The scheme ensures that the timer of the best node, which has the highest metric, expires first. However, it fails to select the best node if another node transmits a packet within Δ s of the transmission by the best node. We derive the optimal metric-to-timer mappings for the practical scenario where the number of nodes is unknown. We consider two cases in which the probability distribution of the number of nodes is either known a priori or is unknown. In the first case, the optimal mapping maximizes the success probability averaged over the probability distribution. In the second case, a robust mapping maximizes the worst case average success probability over all possible probability distributions on the number of nodes. Results reveal that the proposed mappings deliver significant gains compared to the mappings considered in the literature. [ABSTRACT FROM AUTHOR]

An opportunistic, rate-adaptive system exploits multi-user diversity by selecting the best node, which has the highest channel power gain, and adapting the data rate to selected node's channel gain. Since channel knowledge is local to a node, we propose using a distributed, low-feedback timer backoff scheme to select the best node. It uses a mapping that maps the channel gain, or, in general, a real-valued metric, to a timer value. The mapping is such that timers of nodes with higher metrics expire earlier. Our goal is to maximize the system throughput when rate adaptation is discrete, as is the case in practice. To improve throughput, we use a pragmatic selection policy, in which even a node other than the best node can be selected. We derive several novel, insightful results about the optimal mapping and develop an algorithm to compute it. These results bring out the inter-relationship between the discrete rate adaptation rule, optimal mapping, and selection policy. We also extensively benchmark the performance of the optimal mapping with several timer and opportunistic multiple access schemes considered in the literature, and demonstrate that the developed scheme is effective in many regimes of interest. [ABSTRACT FROM AUTHOR]

In a communication system in which K nodes communicate with a central sink node, the following problem of selection often occurs. Each node maintains a preference number called a metric, which is not known to other nodes. The sink node must find the `best' node with the largest metric. The local nature of the metrics requires the selection process to be distributed. Further, the selection needs to be fast in order to increase the fraction of time available for data transmission using the selected node and to handle time-varying environments. While several selection schemes have been proposed in the literature, each has its own shortcomings. We propose a novel, distributed selection scheme that generalizes the best features of the timer scheme, which requires minimal feedback but does not guarantee successful selection, and the splitting scheme, which requires more feedback but guarantees successful selection. The proposed scheme introduces several new ideas into the design of the timer and splitting schemes. It explicitly accounts for feedback overheads and guarantees selection of the best node. We analyze and optimize the performance of the scheme and show that it is scalable, reliable, and fast. We also present new insights about the optimal timer scheme. [ABSTRACT FROM AUTHOR]