My research interests involve the application of operations research (OR) techniques to solve problems encountered by industry and the military. In particular, I’m interested in leveraging the capabilities of (semi-) autonomous vehicles for logistics and surveillance. This includes routing and scheduling of unmanned aerial vehicles (UAVs, also known as drones). I am a Federal Aviation Administration (FAA) certified drone pilot.
Recent test flights at UB’s SOAR drone test facility. Here, we are trying to launch/land drones on a ground rover. Photo: Douglas LevereThe Optimator Lab, housed in Bell Hall, features an immersive drone simulator. The lab serves as a remote command center for SOAR.
“On a summery day in March, the huge mesh drone cage at the University at Buffalo’s North Campus is humming as engineering professor Chase Murray and doctoral student Dowon Lee practice landing remote- and voice-controlled drones on a small autonomous land rover.
It looks like fun, but it’s also part of serious research on how artificial intelligence can equip fleets of drones to launch from the roof of a delivery vehicle and fly packages to customers who live farther from a distribution center than drones can fly.” … Continue reading at buffalonews.com
New Paper – A Graph-Based Approach for Relating Integer Programs (March, 2024):
Abstract. This paper presents a framework for classifying and comparing instances of integer linear programs (ILPs) based on their mathematical structure. It has long been observed that the structure of ILPs can play an important role in determining the effectiveness of certain solution techniques; those that work well for one class of ILPs are often found to be effective in solving similarly structured problems. In this work, the structure of a given ILP instance is captured via a graph-based representation, where decision variables and constraints are described by nodes, and edges denote the presence of decision variables in certain constraints. Using machine learning techniques for graph-structured data, we introduce two approaches for leveraging the graph representations for relating ILPs. In the first approach, a graph convolutional network (GCN) is used to classify ILP graphs as having come from one of a known number of problem classes. The second approach makes use of latent features learned by the GCN to compare ILP graphs to one another directly. As part of the latter approach, we introduce a formal measure of graph-based structural similarity. A series of empirical studies indicate strong performance for both the classification and comparison procedures. Additional properties of ILP graphs, namely, losslessness and permutation invariance, are also explored via computational experiments.
bin packing problem with item fragmentation
capacitated vehicle routing problem
lot sizing problem
generalized assignment problem
Integer linear programming graphs for instances from four different problem classes. These instances were downloaded from strIPlib. Graph visualizations were generated using the Python package networkx. The paper shows how these graphs of integer programs can be used to compare/relate different problem formulations.
My research group has developed several software packages, including:
Drone Ground Control Station
The gallery below shows some screenshots of the ground control station we are developing.
Simulated trailer and real photoFront gatesMission and weather forecastChat and mission planningSimulated video feedLooking thru the trees
Key Features:
Supports a mix of real and virtual (simulated) vehicles, including drones and UGVs.
Provides voice-activated functionality for controlling drones (“move forward 2 meters”) and for obtaining information about the system (“what’s 107’s altitude?”) and surroundings (“what’s the weather?”).
Includes a detailed 3D digital twin of the SOAR drone testing facility
Supports PX4 calibration.
Includes a photo/video gallery
Camera controls for aruco tags
Supports multiple users and text- or voice-based “chat”
Integration with social media accounts
3D mission planning and geofencing capabilities
Generates 3D maps of WiFi signal strength
Import 3D models to test, for example, infrastructure inspection operations
Web-based Robot Control
The open-source ub_web repository contains code for a ROS-enabled webpage. This isn’t nearly as feature-rich as the ground control station; it’s designed to provide some starter code to highlight these types of interactivity:
“Touchpad” controls on mobile devices. These can be used, for example, to control drones.
“Direction Pad” controls (on mobile and desktop). These are discrete buttons, like “move forward” or “stop”.
Support for gamepads (like XBox or PS5 controllers). Connect your gamepad to your phone/computer and press a button. The gamepad should be instantly recognized.
Support for speech-to-text via the Whisper API. This has been successfully tested on Android and Ubuntu devices. It fails to work on Mac/iOS devices. I don’t use Windows.
Video streams from ROS compressed image topics, or mjpg streams.
A “console” to display messages. The system can be run on a network with multiple users in “chat” mode.
This open-source software package, for Python and with web-based components, is designed to help vehicle routing researchers easily create test problems, generate time and distance matrices, and visualize solutions with dynamic 3D movies. Visit veroviz.org for installation instructions, documentation, and examples.
tex2solver makes it easy to transfer LaTeX-typeset optimization models to programming code for use in a solver. Simply copy-and-paste your LaTeX code (or take a screenshot of your model), then choose your desired solver and programming language. tex2solver will generate the code you need to be able to solve instances of your model. With tex2solver, it’s easy to keep your math model and solver code in sync.
My lab has been working on drone-assisted last-mile delivery for over a decade, starting with The Flying Sidekick Traveling Salesman Problem (2015). Co-author Amanda Chu and I proposed two new extensions to the traveling salesman problem (TSP). The resulting problems pair traditional delivery trucks with unmanned aerial vehicles (UAVs, also known as drones).
mFSTSP – In 2020, the “multiple flying sidekicks traveling salesman problem” was published in Transportation Research Part C. This paper features models and algorithms for problems involving a single delivery truck an multiple delivery drones.
mFSTSP with Variable Drone Speeds – Fly Slower to Reduce Drone Delivery Times? Another 2020 paper with Ritwik Raj revealed that flying drones at slower speeds can actually lead to a significant reduction in overall delivery times.
Truck/Drone deliveries with road traffic – The 3rd paper from Ritwik Raj’s Ph.D. dissertation involved “The Time-Dependent Multiple Flying Sidekicks Traveling Salesman Problem”. Dr. Raj’s research examines the impacts of road network congestion in a last-mile delivery system consisting of a truck and multiple drones. Existing literature in this area assumes that the truck travel time between two nodes is fixed. However, this assumption may be dangerous considering that unmanned aerial vehicles (UAVs, or drones) have limited endurance, as congestion may delay the truck’s arrival at retrieval locations, potentially causing crashes. This work introduces the time-dependent multiple flying sidekicks traveling salesman problem, in which truck travel times on each road segment may vary throughout the day. A mixed integer linear programing formulation is provided for small-scale problems, while an ant-pair colony system heuristic is proposed for problems of realistic scale. Results indicate significant improvement in terms of feasibility and time savings over the case in which schedules are generated by neglecting congestion. Furthermore, the analysis demonstrates the ability of the proposed model to increase the utilization of UAVs and smaller roads during high congestion to minimize overall delivery time.
Drone Scheduling with Weather Considerations – The first paper from Dr. Lan Peng’s dissertation, entitled “Parallel Drone Scheduling Traveling Salesman Problem with Weather Impacts” provides a model for scheduling drone and truck operations when inclement weather (e.g., rain, wind, low visibility) restricts flights. A mixed integer linear programming formulation is presented, as well as an efficient heuristic for solving problems of practical size.
