1 paper accepted to ACC

Our paper on closed-form Minkowski sum approximations [1] has been accepted to the American Control Conference!

[1] J. Guthrie, M. Kobilarov, and E. Mallada, “Closed-Form Minkowski Sum Approximations for Efficient Optimization-Based Collision Avoidance,” in American Control Conference (ACC), 2022, pp. 1-7.
[Bibtex] [Abstract] [Download PDF]

Motion planning methods for autonomous systems based on nonlinear programming offer great flexibility in incorporating various dynamics, objectives, and constraints. One limitation of such tools is the difficulty of efficiently representing obstacle avoidance conditions for non-trivial shapes. For example, it is possible to define collision avoidance constraints suitable for nonlinear programming solvers in the canonical setting of a circular robot navigating around $M$ convex polytopes over $N$ time steps. However, it requires introducing $(2+L)MN$ additional constraints and $LMN$ additional variables, with $L$ being the number of halfplanes per polytope, leading to larger nonlinear programs with slower and less reliable solving time. In this paper, we overcome this issue by building closed-form representations of the collision avoidance conditions by outer-approximating the Minkowski sum conditions for collision. Our solution requires only $MN$ constraints (and no additional variables), leading to a smaller nonlinear program. On motion planning problems for an autonomous car and quadcopter in cluttered environments, we achieve speedups of 4.0x and 10x respectively with significantly less variance in solve times and negligible impact on performance arising from the use of outer approximations.

@inproceedings{gkm2022acc,
  abstract = {Motion planning methods for autonomous systems based on nonlinear programming offer great flexibility in incorporating various dynamics, objectives, and constraints. One limitation of such tools is the difficulty of efficiently representing obstacle avoidance conditions for non-trivial shapes. For example, it is possible to define collision avoidance constraints suitable for nonlinear programming solvers in the canonical setting of a circular robot navigating around $M$ convex polytopes over $N$ time steps. However, it requires introducing $(2+L)MN$ additional constraints and $LMN$ additional variables, with $L$ being the number of halfplanes per polytope, leading to larger nonlinear programs with slower and less reliable solving time. In this paper, we overcome this issue by building closed-form representations of the collision avoidance conditions by outer-approximating the Minkowski sum conditions for collision. Our solution requires only $MN$ constraints (and no additional variables), leading to a smaller nonlinear program. On motion planning problems for an autonomous car and quadcopter in cluttered environments, we achieve speedups of 4.0x and 10x respectively with significantly less variance in solve times and negligible impact on performance arising from the use of outer approximations.},
  author = {Guthrie, James and Kobilarov, Marin and Mallada, Enrique},
  booktitle = {American Control Conference (ACC)},
  grants = {CAREER-1752362, CPS-2136324, TRIPODS-1934979},
  month = {2},
  pages = {1-7},
  pubstate = {accepted},
  record = {accepted, submitted Oct. 2021},
  title = {Closed-Form Minkowski Sum Approximations for Efficient Optimization-Based Collision Avoidance},
  url = {https://mallada.ece.jhu.edu/pubs/2021-Preprint-GKM.pdf},
  year = {2022}
}

1 paper accepted to PSCC

Our paper on market mechanism for truthful bidding with energy storage [1] have been accepted to The Power Systems Computation Conference!

[1] R. K. Bansal, P. You, D. F. Gayme, and E. Mallada, “A Market Mechanism for Truthful Bidding with Energy Storage,” in Power Systems Computation Conference (PSCC), 2022, pp. 1-9.
[Bibtex] [Abstract] [Download PDF]

This paper proposes a market mechanism for multiinterval electricity markets with generator and storage participants. Drawing ideas from supply function bidding, we introduce a novel bid structure for storage participation that allows storage units to communicate their cost to the market using energycycling functions that map prices to cycle depths. The resulting market-clearing process–implemented via convex programming–yields corresponding schedules and payments based on traditional energy prices for power supply and per-cycle prices for storage utilization. We illustrate the benefits of our solution by comparing the competitive equilibrium of the resulting mechanism to that of an alternative solution that uses prosumer-based bids. Our solution shows several advantages over the prosumerbased approach. It does not require a priori price estimation. It also incentivizes participants to reveal their truthful cost, thus leading to an efficient, competitive equilibrium. Numerical experiments using New York Independent System Operator (NYISO) data validate our findings.

@inproceedings{bygm2022pscc,
  abstract = {This paper proposes a market mechanism for multiinterval electricity markets with generator and storage participants. Drawing ideas from supply function bidding, we introduce a novel bid structure for storage participation that allows storage units to communicate their cost to the market using energycycling functions that map prices to cycle depths. The resulting market-clearing process--implemented via convex programming--yields corresponding schedules and payments based on traditional energy prices for power supply and per-cycle prices for storage utilization. We illustrate the benefits of our solution by comparing the competitive equilibrium of the resulting mechanism to that of an alternative solution that uses prosumer-based bids. Our solution shows several advantages over the prosumerbased approach. It does not require a priori price estimation. It also incentivizes participants to reveal their truthful cost, thus leading to an efficient, competitive equilibrium. Numerical experiments using New York Independent System Operator (NYISO) data validate our findings.},
  author = {Bansal, Rajni Kant and You, Pengcheng and Gayme, Dennice F. and Mallada, Enrique},
  booktitle = {Power Systems Computation Conference (PSCC)},
  grants = {CAREER-1752362, TRIPODS-1934979, CPS-2136324},
  month = {7},
  pages = {1-9},
  record = {accepted Feb. 2022, submitted Oct. 2021},
  title = {A Market Mechanism for Truthful Bidding with Energy Storage},
  url = {https://mallada.ece.jhu.edu/pubs/2021-Preprint-BYGM.pdf},
  year = {2022}
}

1 paper accepted to SICON

Our paper on delays and saturation in contact tracing for disease control [1] have been accepted to SIAM Journal of Control and Optimization!

[1] Unknown bibtex entry with key [pfpypm2021sicon]
[Bibtex]

Rajni passes his GBO

Rajni Kant Bansal, ME Ph.D. student from our lab, passed his Graduate Board Oral Examination! Congratulations!

1 paper accepted to CDC 21

Our paper on tight inner approximation of the positive-semidefinite cone [1] have been accepted to IEEE Conference on Decision and Control!

[1] [doi] T. Zheng, J. Guthrie, and E. Mallada, “Inner Approximations of the Positive-Semidefinite Cone via Grassmannian Packings,” in 60th IEEE Conference on Decision and Control (CDC), 2021, pp. 981-986.
[Bibtex] [Abstract] [Download PDF]

We investigate the problem of finding tight inner approximations of large dimensional positive semidefinite (PSD) cones. To solve this problem, we develop a novel decomposition framework of the PSD cone by means of conical combinations of smaller dimensional sub-cones. We show that many inner approximation techniques could be summarized within this framework, including the set of (scaled) diagonally dominant matrices, Factor-width k matrices, and Chordal Sparse matrices. Furthermore, we provide a more flexible family of inner approximations of the PSD cone, where we aim to arrange the sub-cones so that they are maximally separated from each other. In doing so, these approximations tend to occupy large fractions of the volume of the PSD cone. The proposed approach is connected to a classical packing problem in Riemannian Geometry. Precisely, we show that the problem of finding maximally distant sub-cones in an ambient PSD cone is equivalent to the problem of packing sub-spaces in a Grassmannian Manifold. We further leverage the existing computational methods for constructing packings in Grassmannian manifolds to build tighter approximations of the PSD cone. Numerical experiments show how the proposed framework can balance accuracy and computational complexity, to efficiently solve positive-semidefinite programs.

@inproceedings{zgm2021cdc,
  abstract = {We investigate the problem of finding tight inner approximations of large dimensional positive semidefinite (PSD) cones. To solve this problem, we develop a novel decomposition framework of the PSD cone by means of conical combinations of smaller dimensional sub-cones. We show that many inner approximation techniques could be summarized within this framework, including the set of (scaled) diagonally dominant matrices, Factor-width k matrices, and Chordal Sparse matrices. Furthermore, we provide a more flexible family of inner approximations of the PSD cone, where we aim to arrange the sub-cones so that they are maximally separated from each other. In doing so, these approximations tend to occupy large fractions of the volume of the PSD cone. The proposed approach is connected to a classical packing problem in Riemannian Geometry. Precisely, we show that the problem of finding maximally distant sub-cones in an ambient PSD cone is equivalent to the problem of packing sub-spaces in a Grassmannian Manifold. We further leverage the existing computational methods for constructing packings in Grassmannian manifolds to build tighter approximations of the PSD cone. Numerical experiments show how the proposed framework can balance accuracy and computational complexity, to efficiently solve positive-semidefinite programs.},
  author = {Zheng, Tianqi and Guthrie, James and Mallada, Enrique},
  booktitle = {60th IEEE Conference on Decision and Control (CDC)},
  doi = {10.1109/CDC45484.2021.9682923},
  grants = {EPCN-1711188, CAREER-1752362, AMPS-1736448, TRIPODS-1934979},
  month = {12},
  pages = {981-986},
  record = {presented Dec. 2022, accepted Jul. 2021, submitted Mar. 2021},
  title = {Inner Approximations of the Positive-Semidefinite Cone via Grassmannian Packings},
  url = {https://mallada.ece.jhu.edu/pubs/2021-CDC-ZGM.pdf},
  year = {2021}
}

Yan and Charalampos defended their dissertations

Yan has defended her dissertation entitled “Leveraging Inverter-Interfaced Energy Storage for Frequency Control in Low-Inertia Power Systems” on Tuesday, June 29th!

Charalampos has defended his dissertation entitled “Designing resilient interdependent infrastructures across spatial and temporal scales” on Wednesday, June 30th!

Congratulations, Yan and Charalampos!