Many real-world systems can be modeled as graphs, where nodes store and consume entities, actively produce them, or have them emerge naturally, and edges transport them between nodes. This paper studies the networked control problem on such large-scale systems, aiming to decide production and transportation over time to maximize long-term profits, subject to node or edge capacity constraints. Existing SOTAs either fail to guarantee feasibility or cannot scale to large-scale systems. We propose a two-stage policy that integrates a constrained optimization layer after a neural network to explicitly enforce constraints and ensure feasibility. By leveraging the problem structure to obtain expert actions and designing a decision-focused and differentiable loss to enable imitation learning, our method significantly improves efficiency and scalability. In small-scale systems with action dimensions in the order of 10, our method achieves 60x sample efficiency over SOTAs on average. In large-scale systems with action dimensions ranging from 100 to 100000, where SOTAs fail to train, our method converges quickly and outperforms non-learning-based baselines significantly.

Tiny cameras are ubiquitous in embedded devices like smart glasses and drones. On-device learning technique empowers these resource-constrained devices to adapt to changing environments locally. However, existing camera modules rely on diverse programming environments and APIs. This heterogeneity impedes the validation and deployment of practical on-device learning algorithms. In this work, we introduce CamOL, the first full-stack on-device learning scheme for heterogeneous tiny cameras. CamOL integrates a complete workflow encompassing preprocessing, learning, inference, and visualization. For learning, CamOL adopts a library-free code design for maximum portability and programmability, and incorporates a proposed staged training method for efficient full-parameter fine-tuning. For inferring, we have developed a suite of operators and achieved operator fusion for minimal latency. We demonstrate CamOL with a compact, low-cost (<$10) prototype that features an engaging and interactive visualization. This allows participants to intuitively experience the entire on-device learning pipeline for different applications in real-time. Moreover, CamOL can also serve as a handy testbed for embedded vision intelligence.

This paper presents Serafin, the first full-stack, sub-mW, and versatile Bluetooth-enabled RF sensor that brings transparent RF sensing to any mobile and IoT device: it independently conducts the whole RF sensing process from RF signal reception to sensing result computation in a wide variety of sensing tasks with only negligible power consumption. At the core of Serafin are our two designs that address the challenge posed by the stringent sub-mW power constraint to jointly achieving versatility and full stackness. Specifically, (i) we utilize the ambient Bluetooth advertising signal as the signal for sensing, and extract the phase difference of the sensing signals received by each antenna pair from the amplitude of their sum signal, which avoids power-hungry hardware components and intensive computation, and (ii) we employ low-power MCU as the computation hardware, and suppress its power consumption by activating it adaptively only when necessary and customizing a light-weight neural network model that still ensures satisfactory inference accuracy. Our extensive experiments on 6 representative sensing tasks show that Serafin achieves competitive sensing performance, but consumes only around 500–900μW power, which is 3–4 orders of magnitude lower than those of existing full-stack and versatile counterparts.

This paper demonstrates Serafin, the first full-stack, sub-mW, and versatile Bluetooth-enabled RF sensor that brings transparent RF sensing to mobile and IoT device: it independently conducts the whole RF sensing process from RF signal reception to sensing result computation in a wide variety of sensing tasks with only negligible power consumption. At the core of Serafin are our two designs that address the challenge posed by the stringent sub-mW power constraint to jointly achieving versatility and full stackness. Specifically, (i) we utilize the ambient Bluetooth advertising signal as the signal for sensing, and extract the phase difference of the sensing signals received by each antenna pair from the amplitude of their sum signal, which avoids power-hungry hardware components and intensive computation, and (ii) we employ low-power MCU as the computation hardware, and suppress its power consumption by activating it only when necessary and customizing a light-weight yet versatile neural network model.

Fast and accurate sand trash detection and localization is extremely important for trash cleaning, and at present, it still mainly depends on sanitation workers to carry out manual detection. Existing computer vision-based methods cannot detect the shallowly-buried trash. Besides, it is difficult and costly to use ground penetrating radar to detect. To overcome these limitations, we design and implement a novel detection system for shallowly buried trash in sandy land, which integrates the commercial IR-UWB radar into the intelligent unmanned vehicle. By controlling the movement of the vehicle, the radar scans the targeted sandy land and synthesizes the signal into the radar heat-map to detect and locate the shallowly buried trash. Experimental results show that the detection accuracy of the system reaches 92.3% with the radar is 75cm from the ground and the angle perpendicular to the ground is 20°. In the direction parallel to the ground, the farthest trash can be detected is 4.2m away from the radar. Within the range of 4.5m2, it can detect and locate up to 9 trash at the same time.

Achieving optimal order dispatching has been a long-standing challenge for online ride-hailing platforms. Early methods would make shortsighted matchings as they only consider order prices alone as the edge weights in the driver-order bipartite graph, thus harming the platform's revenue. To address this problem, recent works evaluate the value of the order's destination region to be the long-term income a driver could obtain in average in such region and incorporate it into the order's edge weight to influence the matching results. However, they often result in insufficient driver supplies in many regions, as the values evaluated in different regions vary greatly, mainly because the impact of one region's value on the future number of drivers and revenue in other regions is overlooked. This paper models such impact within a cooperative Markov game, which involves each value's impact over the platform's revenue with the goal to find the optimal region values for revenue maximization. To solve this game, our work proposes a novelgoal-reaching collaboration (GRC) algorithm that realizes credit assignment from a novel goal-reaching perspective, addressing the difficulty for accurate credit assignment with large-scale agents of previous methods and resolving the conflict between credit assignment and offline reinforcement learning. Specifically, during training, GRC predicts the city's future state through an environment model and utilizes a scoring model to rate the predicted states to judge their levels of profitability, where high-scoring states are regarded as the goal states. Then, the policies in the game are updated to promote the city to stay in the goal states for as long as possible. To evaluate GRC, we deploy a baseline policy online in several cities for three weeks to collect real-world dataset. Training and testing results on the collected dataset indicate that our GRC consistently outperforms the baselines in different cities and peak periods.

Nowadays, unmanned aerial vehicles (UAVs) are widely applied in crowd sensing. For UAV-enabled crowd sensing (UAVCS) systems, the sensing outcome and charging cost are two primary concerns. To achieve a satisfactory sensing outcome under the charging budget, we exploit joint moving, sensing, and charging scheduling of UAVs, as they all have critical impacts on such two objectives. However, the dynamically generated sensing targets and the variety of sensing tasks a UAVCS system may face make farsighted scheduling of UAVs rather challenging. To this end, we propose a novel multi-task constrained multi-agent reinforcement learning (MARL) method to help UAVs make distributed moving, sensing, and charging decisions. Specifically, we design a multi-task MARL framework to learn a single generic policy for a large collection of tasks, and propose a primal-dual training algorithm that alternates between improving the overall sensing outcome and reducing each task's constraint violation. Theoretically, we show that our algorithm provably converges, and analyze the optimality gap and constraint violation of the trained policy on unseen tasks. Extensive experiments on an incident dataset in New York City demonstrate that our method outperforms strong baselines in sensing outcome maximization and budget satisfaction, and also generalize well to unseen tasks.

The quality of surface water is closely related to human’s production and livelihood. Water salinity is one of the key indicators of water quality assessment. Recently, there has been an increased salinization problem of surface water in many regions of the world, making it necessary to timely monitor the salinity of surface water. Water salinity sensing could be challenging when it comes to surface water with complicated basin and tributaries, where existing methods fail to satisfy both efficiency and accuracy requirements. To address this problem, we propose a novel water salinity sensing system USalt, which leverages the high mobility of UAV and the contactless sensing ability of IR-UWB radar, and realizes fast and accurate water salinity sensing for surface water. Specifically, we design novel methods to eliminate the contamination in raw received radar signals and extract salinity-related features from radar signals. Furthermore, we adopt a neural network model ssNet to precisely estimate water salinity using the extracted features. To efficiently adapt ssNet to different environments, we customize meta learning and design a meta-learning framework mssNet. Extensive real-world experiments carried out by our UAV-based system illustrate that USalt can accurately sense the salinity of water with an MAE of 0.39 g/100 mL.

In recent years, multi-agent reinforcement learning (MARL) has presented impressive performance in various applications. However, physical limitations, budget restrictions, and many other factors usually impose constraints on a multi-agent system (MAS), which cannot be handled by traditional MARL frameworks. Specifically, this paper focuses on constrained MASes where agents work cooperatively to maximize the expected team-average return under various constraints on expected team-average costs, and develops a constrained cooperative MARL framework, named DeCOM, for such MASes. In particular, DeCOM decomposes the policy of each agent into two modules, which empowers information sharing among agents to achieve better cooperation. In addition, with such modularization, the training algorithm of DeCOM separates the original constrained optimization into an unconstrained optimization on reward and a constraints satisfaction problem on costs. DeCOM then iteratively solves these problems in a computationally efficient manner, which makes DeCOM highly scalable. We also provide theoretical guarantees on the convergence of DeCOM's policy update algorithm. Finally, we conduct extensive experiments to show the effectiveness of DeCOM with various types of costs in both moderate-scale and large-scale (with 500 agents) environments that originate from real-world applications.

The rapid development of connected autonomous vehicles (CAVs) makes it foreseeable that CAVs will dominate future road traffic. To manage CAV traffic, researchers developed a revolutionary paradigm, which uses intelligent intersection managers (IMs) for a finer-grained control of CAVs' cruising at intersections than traditional traffic lights. However, existing IM-based methods mostly focus on optimizing the single-intersection CAV traffic efficiency, without solving the fundamental problem of maximizing the global efficiency of a multi-intersection road network. Therefore, we address such problem by proposing a system architecture that decomposes each IM into an oracle and a valve, where the oracle ensures safe and efficient crossing at individual intersections, and the valve selects some of the approaching CAVs for the oracle to control and postpones the crossing of the unselected ones. We further focus on distributed decision making for the valves, and propose a multi-agent reinforcement learning framework, spatial-aware multi-agent actor-credit (SMAC). Specifically, SMAC integrates a novel credit assignment method that captures agents' spatially decaying influences to stimulate agent cooperation, and a novel graph convolutional mixing network to capture the graph-structured inter-agent relationships in a road network. We conduct extensive experiments on three traffic flow datasets, and show that SMAC outperforms state-of-the-art baselines.

For-hire vehicle-enabled crowd sensing (FVCS) has become a promising paradigm to conduct urban sensing tasks in recent years. FVCS platforms aim to jointly optimize both the order-serving revenue as well as sensing coverage and quality. However, such two objectives are often conflicting and need to be balanced according to the platforms’ preferences on both objectives. To address this problem, we propose a novel cooperative multi-objective multi-agent reinforcement learning framework, referred to as MOVDN, to serve as the first preference-configurable order dispatch mechanism for FVCS platforms. Specifically, MOVDN adopts a decomposed network structure, which enables agents to make distributed order selection decisions, and meanwhile aligns each agent’s local decision with the global objectives of the FVCS platform. Then, we propose a novel algorithm to train a single universal MOVDN that is optimized over the space of all preferences. This allows our trained model to produce the optimal policy for any preference. Furthermore, we provide the theoretical convergence guarantee and sample efficiency analysis of our algorithm. Extensive experiments on three real-world ride-hailing order datasets demonstrate that MOVDN outperforms strong baselines and can support the platform in decision-making effectively.

This paper presents EmoRI, a novel single-chip mmWave radar-based egomotion estimation approach that works in challenging scenarios where moving objects exist in radar's Field of View (FoV). Essentially, estimating a mobile platform's egomotion using an on-board mmWave radar requires inferring the relative motion between radar and the points of the stationary objects (PSOs) in the radar point cloud. However, in practice, there could be no PSOs because of the blockage of moving objects. Even if PSOs exist, precisely identifying them is still challenging due to (i) the large quantity of points generated by the moving objects, and (ii) the huge angle estimation errors of the conventional point cloud generation algorithm. We empower EmoRI to overcome the above challenges incurred by moving objects with three core techniques, which include (i) a hybrid FFT-MUSIC algorithm that improves the angle estimation accuracy of single-chip mmWave radar, (ii) a multiple stationary target consensus algorithm that precisely selects the PSOs from the radar point cloud, and (iii) a simultaneous fusion and calibration mechanism that introduces an IMU as the auxiliary sensor, meticulously calibrates IMU accelerations with radar measurements, and complimentarily fuses these two modalities to obtain the 6-DoF egomotion. Our extensive experiments validate that EmoRI pushes the limit of single-chip mmWave radar-based egomotion estimation with moving objects in radar's FoV by reducing the per-meter destination error from decimeter to centimeter level.

Recent years have witnessed the increasing popularity of electric buses (e-buses) around the globe due to their environment friendly nature. However, various factors, such as the prohibitive purchasing costs and the scarcity of large-scale charging facilities, hinder the wider adoption of e-buses. Thus, to effectively cut the cost of building and maintaining urban e-bus systems, we optimize the dispatching strategy for urban e-bus systems to satisfy public transportation demands with the minimum e-bus fleet. Specifically, we propose to systematically exploit at city-scale cross-line dispatching, a smart dispatching strategy allowing one bus to serve multiple bus lines when necessary. Technically, we construct a novel and generalizable graph-theoretic model for urban e-bus systems integrating e-buses non-negligible charging time, the spatio-temporal constraints of bus trips, and various other real-world factors. We prove that it is NP-hard, and has no$(2-\epsilon)$-approximation algorithm. Next, we propose a polynomial-time algorithm solving the problem with a guaranteed approximation ratio. Furthermore, we conduct extensive experiments on a large-scale real-world bus dataset from Shenzhen, China, which validate the effectiveness of our algorithms. As shown by our experimental results, to serve 300 bus lines, our dispatching strategy needs 38.2% less e-buses than the one currently used in practice.

Nowadays, the rapid development of self-driving technology and its fusion with the current vehicle electrification process has given rise to electric self-driving taxis (es-taxis). Foreseeably, es-taxis will become a major force that serves the massive urban mobility demands not far into the future. Though promising, it is still a fundamental unsolved problem of effectively deciding when and where a city-scale fleet of es-taxis should be charged, so that enough es-taxis will be available whenever and wherever ride requests are submitted. Furthermore, charging decisions are far from isolated, but tightly coupled with the order dispatch process that matches orders with es-taxis. Therefore, in this paper, we investigate the problem of joint order dispatch and charging in es-taxi systems, with the objective of maximizing the ride-hailing platform’s long-term cumulative profit. Technically, such problem is challenging in a myriad of aspects, such as long-term profit maximization, partial statistical information on future orders, etc. We address the various arising challenges by meticulously integrating a series of methods, including distributionally robust optimization, primal-dual transformation, and second order conic programming to yield far-sighted decisions. Finally, we validate the effectiveness of our proposed methods though extensive experiments based on two large-scale real-world online ride-hailing order datasets.

Recent years have witnessed the proliferation of electric vehicles (EVs) that enable environment-friendly commuting and traveling. However, the increasing number of EVs inevitably create massive charging demands that are challenging to satisfy. Oftentimes in practice, EVs have to wait in queues for a long time outside charging stations before chargers become available. To address this challenge, we fully capture the elasticity of EVs’ charging demands in response to the charging prices, and propose a dynamic charging pricing mechanism that jointly controls the lengths of the demand queues at multiple charging stations and maximizes the charging platform’s long-term profit for offering charging services. Clearly, such an approach is more feasible than the financially and temporally expensive way of constructing extra charging facilities. Technically, we augment the Lyapunov stochastic optimization technique to decompose the challenging long-term decision-making problem into a series of single-time-slot optimization programs which require zero knowledge of future system parameters. However, due to the correlation of charging demands among different stations, the aforementioned optimization program in each time slot is non-convex. We handle the non-convexity by jointly constructing independent sets of charging stations and adapting the block coordinate descent method to iteratively obtain approximately optimal charging prices. Through rigorous theoretical analysis and extensive simulations based on the real-world dataset in the Chinese city Shenzhen which consists of 4000 taxis and 171 charging stations, we demonstrate that our control policy ensures an arbitrarily close-to-optimal profit with a flexible trade-off between the profit and queue lengths, has a low computational complexity, and requires zero knowledge of future system dynamics.

Nowadays, the urban vehicle sharing (UVS) service offered by online platforms such as Car2Go and Zipcar has become an attractive choice for short-term mobility demands of city residents. Such way of shared mobility also demonstrates its potential in addressing various urban traffic problems (e.g., congestion, exhaust gas emission). However, the power of UVS systems could not be fully unleashed, unless the demand-supply gaps, incurred by the uneven spatial-temporal distributions of vehicle sharing orders and available vehicles, are effectively bridged. In this paper, we propose to resolve such problem by performing joint order dispatch and repositioning, which eventually maximizes the UVS platform's long-term cumulative profit. Specifically, we have addressed the various arising challenges, including capturing the interactive effect between order dispatch and repositioning, incorporating properly vehicles' fuel levels in our model, and dealing with stochastic demand with partially known statistical information. Technically, the problem is formulated as a stochastic dynamic program, and by integrating a series of methods, involving distributionally robust optimization, primal-dual transformation, as well as second order conic programming, we finally yield long-term optimal decisions. Furthermore, we validate our proposed methods using a large-scale real-world UVS dataset with over 300 vehicles and 300 thousand orders spanning overall 18 months.

Electric self-driving taxis (es-taxis) draw great attention nowadays and hold the promise for future transportation due to their convenient and environment-friendly nature. However efficiently managing large-scale es-taxis remains an open problem. In this paper, we focus on scheduling es-taxis under charging budget constraint. Specifically, we design safe-controller to guarantee the satisfaction of budget constraint, and propose HAT framework to enlarge the sight for decision-making on deactivating es-taxis. As for the non-stationary induced by HAT, we analyze and limit its influence with theoretical guarantees. The overall framework Safe-HAT achieves superior performance in real-world data against other strong baselines.

Vehicular urban sensing (VUS), which uses sensors mounted on crowdsourced vehicles or on-board drivers' smartphones, has become a promising paradigm for monitoring critical urban metrics. Due to various hardware and software constraints difficult for private vehicles to satisfy, for-hire vehicles (FHVs) are usually the major forces for VUS systems. However, FHVs alone are far from enough for fine-grained spatio-temporal sensing coverage, because of their severe distribution biases. To address this issue, we propose to use a hybrid approach, where a centralized platform not only leverages FHVs to conduct sensing tasks during their daily movements of serving passenger orders, but also controls multiple dedicated sensing vehicles (DSVs) to bridge FHVs' coverage gaps. Specifically, we aim to achieve fine-grained spatio-temporal sensing coverage at the minimum long-term operational cost by systematically optimizing the repositioning policy for DSVs. Technically, we formulate the problem as a stochastic dynamic program, and solve various challenges, including long-term cost minimization, stochastic demand with partial statistical knowledge, and computational intractability, by integrating distributionally robust optimization, primal-dual transformation, and second order conic programming methods. We validate the effectiveness of our methods using a real-world dataset from Shenzhen, China, containing 726,000 trajectories of 3848 taxis spanning overall 1 month in 2017.

The rapid development of information and communication technologies has given rise to mobility-on-demand (MoD) systems (e.g., Uber, Didi) that have fundamentally revolutionized urban transportation. One common feature of today's MoD systems is the integration of ridesharing due to its cost-efficient and environment-friendly natures. However, a fundamental unsolved problem for such systems is how to serve people's heterogeneous transportation demands with as few vehicles as possible. Naturally, solving such minimum fleet problem is essential to reduce the vehicles on the road to improve transportation efficiency. Therefore, we investigate the fleet minimization problem in ridesharing-aware MoD systems. We use graph-theoretic methods to construct a novel order graph capturing the complicated inter-order shareability, each order's spatial-temporal features, and various other real-world factors. We then formulate the problem as a tree cover problem over the order graph, which differs from the traditional coverage problems. Theoretically, we prove the problem is NP-hard, and propose a polynomial-time algorithm with a guaranteed approximation ratio. Besides, we address the online fleet minimization problem, where orders arrive in an online manner. Finally, extensive experiments on a city-scale dataset from Shenzhen, containing 21 million orders from June 1st to 30th, 2017, validate the effectiveness of our algorithms.

Recent years have witnessed the rising popularity of urban vehicular crowd sensing (UVCS) systems that leverage drivers' mobile devices equipped with on-board sensors for various urban sensing tasks. Because of the importance of ensuring satisfactory spatio-temporal sensing coverage in such UVCS systems, most existing work has focus on designing efficient scheduling mechanisms to maximize the task completion rate under drivers' traveling constraints. Different from prior work, we propose Hector, a joint trajectory scheduling and incentive mechanism for spatio-temporal UVCS systems, which concentrates on capturing the interactive effects between scheduling and incentive mechanisms. Technically, we first reduce the dimensions of the original scheduling problem by mapping it into an augmented set cover problem with spatio-temporal constraints. Then, based on reverse combinatorial auctions, we design Hector, whose incentive mechanism with the presence of uncertain future trajectory information makes scheduling and compensation decisions in real-time. Specifically, Hector is truthful, individual rational and computationally efficient. Furthermore, the social cost yielded by Hector is close-to-optimal, and the approximation ratio is Hm. The advantageous properties of Hector are verified by both rigorous theoretical analysis and extensive simulations based on the real world datasets in the Chinese city Shenzhen which consists of 726,000 taxi trajectories.

With the development of D2D (Device-to- Device) communications, the ever increasingly growing demand for content sharing caused by nearby devices can be satisfied. D2D communications based on social relationships are taken into consideration in extant literature, while how to select friends with whom users share contents efficaciously and voluntarily remains a problem. To this end, social tie, as a measurement of content similarity and mutual trust, is introduced in our work to facilitate contents sharing. In the paper, we first model friend selection problem as a finite horizon optimal stopping problem in the frame of optimal stopping theory and derive the optimal social cost threshold. We further prove the optimal social cost threshold is endowed with monotonically non- decreasing property. Moreover, we develop an iterative algorithm based on derived social cost threshold to select friends with whom users are inclined to share contents. Last but not the least, numerous simulation results validate the effectiveness of our proposed algorithm for content sharing over random D2D communications.