LIDS Research Highlights

Rollout Algorithms

Rollout algorithms provide a method for approximately solving a large class of discrete and dynamic optimization problems. Using a lookahead approach, rollout algorithms leverage repeated use of a greedy algorithm, or base policy, to intelligently make decisions. This technique is easy to implement, inherits performance bounds given by the selected base policy, and performs very well in practice. In some cases the observed performance is near optimal. However, there have been few theoretical results guaranteeing a strict improvement over base policies.

Lifts of polytopes and matrix factorization

Linear programming is an ubiquitous technique used in a wide variety of disciplines, ranging from scheduling and planning in management, to signal processing and control theory in engineering. From a mathematical point of view, linear programming is the problem of maximizing a linear function over a polytope. In order to solve such an optimization problem in practice, it is important to have a concise description of the polytope under consideration. Consider for example the hexagon depicted in Figure 1 (left), which is a simple example of a polytope.

Reducing Control Overheads in Wireless Networks

Network control mechanisms are used to regulate the flow of traffic and ensure effective data transport in communication networks. Examples of network control tasks include scheduling and resource allocation, routing, and flow control. Typically, network control actions are taken in response to changes in the network state. Therefore, network control tasks necessitate the exchange of information regarding the network state, which we refer to as control information or protocol information.

Network control: from theory to practice

The performance and control of communication networks can be analyzed using a beautiful theory based on queue stability. This theory gave us the backpressure algorithm firstly proposed by Tassiulas & Ephremides in 1992 [1], whereby packets flow in the data network according to queue backlog differences (a packet always flows from a highly-backlogged node to a neighboring node with smaller backlog). In the context of the ONR project, Prof. Modiano and his group work towards bridging the gap between this control theory and how real networks work.

Protecting Networks from Large-Scale Physical Attacks and Disasters

Telecommunication networks play a vital role in the day-to-day routine of all sectors of our society. During a crisis, telecommunications is essential to facilitate the control of physically remote agents, provides connections between emergency response personnel, and eventually enables reconstitution of societal functions.

Dynamic pickup and delivery problems with insights about demand-responsive transportation systems

In the last decade, unmanned vehicles have been used increasingly in a number of surveillance and remote sensing applications, to observe and classify unknown “events” which occur in a large workspace over the course of a long mission. Foremost in this domain are unmanned aerial vehicles, or UAVs, which are a major focus for military air forces and also have increasingly non-military applications such as monitoring of livestock, pipelines, or wildfires.