Mixed Initiative and Collaborative Learning in Adversarial Environments (July 2020)
PIs: Claire Tomlin (Lead), Shankar Sastry, Xenofon Koutsoukos, Janos Sztipanovits
HARD PROBLEM(S) ADDRESSED: Human Behavior (primary), Resilient Architectures (secondary), and Scalability and Composability (secondary)
This quarter has been the quarter that the Pandemic hit. Rather than continue to exclusively work on the CPS work on the lack of robustness of AI/ML algorithms we began thinking about the resilience of CPS systems to attack. While there has been a great deal of SoS work on how to have cyber systems operate through attack, there has been almost no work on what it takes to restart a shut-down societal system. We believe that Science and Technology Tools for this work in their infancy. However, a large part of resilience is the ability to restart. I have recruited two young students to work on this. A lot of their work is quite new but I will give you a summary of the work. The publications are in progress.
PUBLICATIONS (from the current quarter only; pending publications go in section 2 below)
- Victoria Tuck, Kshitij Kulkarni, Theo Cabanes, Alex Bayen and Shankar Sastry, “Understanding speed limit restrictions as Pigovian taxes with imperfect differentiation in road traffic”, (to be submitted to ICCPS, 2021 in September 2020). It is widely suspected that when the pandemic ends that there will be more private transportation on the roads. There will be a need to diert traffic off the main freeways onto side streets so as to maintain throughput (traffic apps such as Waze, Google, etc. are already doing this). Neighborhoods close to freeways are resisting by imposing “draconian” speed limits on by pass traffic. This is a denial of service attack on commuters. In this paper we provide policy alternatives to resolve the competitng needs of the traffic infrastructure and neighborhood traffic.
We show that a decrease in speed limit can be interpreted as a Pigovian tax with imperfect differentiation in routing games (with travel time being interpreted as a price to pay to travel). In routing games, vehicles choose paths to minimize their own travel time between their origin and their destination. As a result, some local roads near congested highways get Ihigher flow that the one they are designed to sustain creating negative externalities for cities. In this article, we consider the case where one city has the ability to influence traffic by decreasing or increasing the speed limit on city roads. We show that decreasing speed limits inside the city can improve city’s social welfare by incentivizing cut-through travelers to not use local roads. A trade-off is exhibited between residential accessibility (increasing the speed limit) and residential safety (decreasing the speed limit to decrease flow on local roads) on this benchmark framework. The article shows that decreasing speed limits is not optimal because it uniformly taxes every vehicle (residents and cut-through travelers), but a route-based pricing is optimal as it enables to specifically tax the flow responsible for the externality. Finally, we show that Pigovian taxes applied both uniformly and with differentiation improve network congestion above that caused by the Wardrop equilibrium - Kshitij Kulkarni and Sven Nath, “The Puzzle of Useful Advice”, (preprint to be submitted for publication, May 2020). In social choice theory, we investigate how a policy maker should deal with a population whose preferences are changing over time. We model social choice problems as Markov Decision Processes (MDP), which allows us to draw on the large computer science literature on dynamic programming and modern reinforcement learning. We also provide a simple counterexample that shows why modeling sequential decision-making is valuable in problems of providing useful advice. Thus, we show how social choice theory can provide useful advice to policy-makers in non-ideal circumstances (when preferences are changing over time). Our key contribution is to introduce a puzzle of useful advice, which is the (unresolved) question how normative theories can offer useful advice to non-ideal agents. The problem here is cast in the framework of building a beneficial artificial agent. We seek to provide philosophical foundations and begin to resolving the issues that arise when attempting to provide feedback to less-than-ideal agents (either groups or individuals). Providing useful advice is difficult in at least two ways: 1) useful advice must improve the decision-making of the agent to which the advice is given, which involves understanding the agent's preferences and ways in which they do not satisfy the axioms of a normative theory and 2) useful advice must be able to be communicated and understood. We also note the constructive nature of the models we introduce, which bring decision theory and social choice theory one step closer to computational implementation.
KEY HIGHLIGHTS
Each effort should submit one or two specific highlights. Each item should include a paragraph or two along with a citation if available. Write as if for the general reader of IEEE S&P.
The purpose of the highlights is to give our immediate sponsors a body of evidence that the funding they are providing (in the framework of the SoS lablet model) is delivering results that "more than justify" the investment they are making
We do not as yet have results on the main topic of resilience that we are working on. However, the highlight thus far has been a development of an understanding of the linking between infection models for disease spread (referred to as SEIR models (Susceptible, Exposed, Infected, Recovered models), social distancing, partial shut downs, contact tracing with models of economic activity. In fine grained regions. We are in the midst of formulating models of optimal decision making to open up sectors of the economy: transportation, retail, schools, etc. while keeping acceptable bounds on disease. The methods being developed involve a complex mixture of AI/ML applied to large data sets which are publicly available and model parameter estimation. The techniques are ones which will have widespread applicability to other classes of networks under cyber (or natural) attacks.
COMMUNITY ENGAGEMENTS
Claire Tomlin ran the 6th installment of Berkeley Girls in Engineering (GiE), a program held at UC Berkeley for middle school students, in Summer 2020. Traditionally, the program runs for 4 weeks, with 30 students participating per week, for a total of 120 students each summer. This year, it was offerd in a virtual format, in which we are preparing a kit, as well as a lended chromebook and wifi hotspot access for each participant. This year it was run virtually with packets that were sent out ahead of time. Ms. Victoria Tuck taught some of the modules at this years GiE.
Shankar Sastry launched a new Institute entitled the C3 Digital Transformation Institute (https://c3dti.ai) a partnership of Berkeley, UIUC (co-leads) with UChicago, CMU, MIT, Princeton, Stanford to develop the science and technology of Digital Transformation. The private philanthropy that supports this institute was very much leveraged on the support of Federal research such as this SoS lablet.
EDUCATIONAL ADVANCES
We are developing a new course in systems theory at Berkeley, to be taken by upper level undergraduates and first and second year graduate students, on a rapprochement between control theory and reinforcement learning. The course will focus on a modern viewpoint on modeling, analysis, and control design, leveraging tools and successes from both systems and control theory and machine learning. The first version of this course was taught by Shankar Sastry in Spring 2020 (ending in May 2020). This course was notable for the rich work it feaured in multi-agent systems.