Publications

We consider the problem of minimizing emission of a heavy-duty truck transporting freight between two locations subject to a hard deadline constraint. The truck is equipped with a multi-speed transmission and a modern combustion engine that intelligently switches among multiple fuel injection strategies at certain engine speeds (called switching speeds) to achieve lower emission profiles. Our objective is to minimize the emission by optimizing both path and speed planning for heavy-duty trucks with multi-speed transmission and multiple injection strategies in the engine. This emission minimization problem, while pervasive in practice, has two challenges: i) the emission rate function is discontinuous and non-convex due to switching of the fuel injections and gear ratios, which makes the common practice of driving at a constant speed on a road segment not eco-friendly; ii) the problem is NP-hard due to the combinatorial nature of the simultaneous path and speed planning. We tackle the first challenge by considering the case where the truck can travel at a heterogeneous speed profile over a road segment and then formulate the speed planning problem as a convex problem. We further identify special structures in this problem and provide an efficient method for computing the optimal speed profile. We then tackle the second challenge by developing an efficient heuristic for both path planning and speed planning to solve the emission minimization problem on the scale of national highway systems. Our extensive simulations on the US highway system show that our solution reduces up to 46% NOx emission as compared to the commonly-adopted fastest path approach. We also find that optimizing heterogeneous speed profiles reduce up to 32% emission as compared to their homogeneous counterpart, thus are necessary to be considered in eco-friendly truck operations.

We consider the scenario where an energy harvesting source sends its updates to a receiver. The source optimizes its energy allocation over a decision period to maximize a sum of time-varying functions of the age of information (AoI), representing the value of providing timely information. In a practical online setting, we need to make irrevocable energy allocation decisions at each time while the time-varying functions and the energy arrivals are only revealed sequentially. The problem is then challenging as 1) we are facing uncertain energy harvesting arrivals and time-varying functions, and 2) the energy allocation decisions and the energy harvesting process are coupled due to the capacity-limited battery. In this paper, we develop an optimal online algorithm CR-Reserve and show it achieves (lnθ+1)-competitive, where θis a parameter representing the level of uncertainty of the time-varying functions. It is the optimal competitive ratio among all deterministic and randomized online algorithms. We conduct simulations based on real-world traces and compare our algorithms with conceivable alternatives. The results show that our algorithms achieve 12% performance improvement as compared to the state-of-the-art baseline.,

Carbon footprint optimization (CFO) is important for sustainable heavy-duty e-truck transportation. We consider the CFO problem for timely transportation of e-trucks, where the truck travels from an origin to a destination across a national highway network subject to a deadline. The goal is to minimize the carbon footprint by orchestrating path planning, speed planning, and intermediary charging planning. We first show that it is NP-hard even just to find a feasible CFO solution. We then develop a (1+\epsilon_F, 1+\epsilon_β) bi-criteria approximation algorithm that achieves a carbon footprint within a ratio of (1+\epsilon_F) to the minimum with no deadline violation and at most a ratio of (1+\epsilon_β) battery capacity violation (for any positive \epsilon_F and \epsilon_β). Its time complexity is polynomial in the size of the highway network, 1/\epsilon_F, and 1/\epsilon_β. Such algorithmic results are among the best possible unless P=NP. Simulation results based on real-world traces show that our scheme reduces up to 11% carbon footprint as compared to baseline alternatives considering only energy consumption but not carbon footprint.

We study the carbon footprint optimization (CFO) of a heavy-duty e-truck traveling from an origin to a destination across a national highway network subject to a hard deadline, by optimizing path planning, speed planning, and intermediary charging planning. Such a CFO problem is essential for carbon-friendly e-truck operations. However, it is notoriously challenging to solve due to (i) the hard deadline constraint, (ii) positive battery state-of-charge constraints, (iii) non-convex carbon footprint objective, and (iv) enormous geographical and temporal charging options with diverse carbon intensity. Indeed, we show that the CFO problem is NP-hard. As a key contribution, we show that under practical settings it is equivalent to finding a generalized restricted shortest path on a stage-expanded graph, which extends the original transportation graph to model charging options. Compared to alternative approaches, our formulation incurs low model complexity and reveals a problem structure useful for algorithm design. We exploit the insights to develop an efficient dual-subgradient algorithm that always converges. As another major contribution, we prove that (i) each iteration only incurs polynomial-time complexity, albeit it requires solving an integer charging planning problem optimally, and (ii) the algorithm generates optimal results if a condition is met and solutions with bounded optimality loss otherwise. Extensive simulations based on real-world traces show that our scheme reduces up to 28% carbon footprint compared to baseline alternatives. The results also demonstrate that e-truck reduces 56% carbon footprint than internal combustion engine trucks.

We implement a new version of E2Pilot, the first energy-efficient navigation system for long-haul timely truck transportation with fast response time and user-friendly interfaces. Given the origin, destination, and delivery time window, E2Pilot provides the path and speed instructions shown on the user interfaces for the truck drivers to transport freights on time with minimum fuel consumption. E2Pilot has two user interfaces: a publicly available website, and a GPS-like smartphone application that provides in-place driving instructions along with off-route detection and re-routing.

We study an online inventory trading problem where a user seeks to maximize the aggregate revenue of trading multiple inventories over a time horizon. The trading constraints and concave revenue functions are revealed sequentially in time, and the user needs to make irrevocable decisions. The problem has wide applications in various engineering domains. Existing works employ the primal-dual framework to design online algorithms with sub-optimal, albeit near-optimal, competitive ratios (CR). We exploit the problem structure to develop a new divide-and-conquer approach to solve the online multi-inventory problem by solving multiple calibrated single-inventory ones separately and combining their solutions. The approach achieves the optimal CR of \ln θ + 1 if N≤\ln θ + 1, where N is the number of inventories and θ represents the revenue function uncertainty; it attains a CR of 1/[1-e^-1/(\lnθ+1) ] in [\ln θ +1, \ln θ +2) otherwise. The divide-and-conquer approach reveals novel structural insights for the problem, (partially) closes a gap in existing studies, and generalizes to broader settings. For example, it gives an algorithm with a CR within a constant factor to the lower bound for a generalized one-way trading problem with price elasticity with no previous results. When developing the above results, we also extend a recent CR-Pursuit algorithmic framework and introduce an online allocation problem with allowance augmentation, both of which can be of independent interest.

We carry out a comparative study of energy consumption of the conventional internal combustion truck and the modern electric truck, traveling from origin to destination over the national highway subject to a hard deadline. We focus on understanding energy saving of the latter over the former and key contributing factors. Our study is unique in that (i) it is based on extensive simulations using real-world data over the U.S. highway system, and (ii) we factor in the power system energy-conversion efficiency when calculating the energy consumption of electric trucks for fair comparison. The results show that on average the electric truck save 10% energy as compared to the internal combustion truck, and this saving will improve as power systems incorporate more renewable generation. Furthermore, the energy saving mainly comes from the energy efficiency of electric motors, and other electric-truck features, e.g., regenerative breaking, only have minor contributions.

Massive device connectivity in Internet of Thing (IoT) networks with sporadic traffic poses significant communication challenges. To overcome this challenge, the serving base station is required to detect the active devices and estimate the corresponding channel state information during each coherence block. The corresponding joint activity detection and channel estimation problem can be formulated as a group sparse estimation problem, also known under the name “Group Lasso”. This letter presents a fast and efficient distributed algorithm to solve such Group Lasso problems, which alternates between solving small-scaled problems in parallel and dealing with a linear equation for consensus. Numerical results demonstrate the speedup of this algorithm compared with the state-of-the-art methods in terms of convergence speed and computation time.

This paper presents a distributed optimization algorithm tailored for solving optimal control problems arising in multi-building coordination. The buildings coordinated by a grid operator, join a demand response program to balance the voltage surge by using an energy cost defined criterion. In order to model the hierarchical structure of the building network, we formulate a distributed convex optimization problem with separable objectives and coupled affine equality constraints. A variant of the Augmented Lagrangian based Alternating Direction Inexact Newton (ALADIN) method for solving the considered class of problems is then presented along with a convergence guarantee. To illustrate the effectiveness of the proposed method, we compare it to the Alternating Direction Method of Multipliers (ADMM) by running both an ALADIN and an ADMM based model predictive controller on a benchmark case study.

The motion of planar ground vehicles is often non-holonomic, and as a result may be modelled by the 2 DoF Ackermann steering model. We analyse the feasibility of estimating such motion with a downward facing camera that exerts fronto-parallel motion with respect to the ground plane. This turns the motion estimation into a simple image registration problem in which we only have to identify a 2-parameter planar homography. However, one difficulty that arises from this setup is that ground-plane features are indistinctive and thus hard to match between successive views. We encountered this difficulty by introducing the first globally-optimal, correspondence-less solution to plane-based Ackermann motion estimation. The solution relies on the branch-and-bound optimisation technique. Through the low-dimensional parametrisation, a derivation of tight bounds, and an efficient implementation, we demonstrate how this technique is eventually amenable to accurate real-time motion estimation. We prove its property of global optimality and analyse the impact of assuming a locally constant centre of rotation. Our results on real data finally demonstrate a significant advantage over the more traditional, correspondence-based hypothesise-and-test schemes.

The problem of guaranteed parameter estimation (GPE) consists in enclosing the set of all possible parameter values, such that the model predictions match the corresponding measurements within prescribed error bounds. One of the bottlenecks in GPE algorithms, commonly exploiting set inversion, is the construction of enclosures for the image-set of factorable functions. In this paper, we introduce a novel set-based computing method called interval superposition arithmetics (ISA) for the construction of enclosures of such image sets and its use in GPE algorithms. The main benefits of using ISA in the context of GPE lie in the improvement of enclosure accuracy and in the implied reduction of the number of set-membership tests in the set-inversion algorithm.