Suresh Jagannathan on higher-order program verification

 |   |  Conversations

Suresh Jagannathan portrait Dr. Suresh Jagannathan joined DARPA in September 2013. His research interests include programming languages, compilers, program verification, and concurrent and distributed systems.

Prior to joining DARPA, Dr. Jagannathan was a professor of computer science at Purdue University. He has also served as visiting faculty at Cambridge University, where he spent a sabbatical year in 2010; and as a senior research scientist at the NEC Research Institute in Princeton, N.J.

Dr. Jagannathan has published more than 125 peer-reviewed conference and journal publications and has co-authored one textbook. He holds three patents. He serves on numerous program and steering committees, and is on the editorial boards of several journals.

Dr. Jagannathan holds Doctor of Philosophy and Master of Science degrees in Electrical Engineering and Computer Science from the Massachusetts Institute of Technology. He earned a Bachelor of Science degree in Computer Science from the State University of New York, Stony Brook.

Luke Muehlhauser: From your perspective, what are some of the most interesting or important developments in higher-order verification in the past decade?


Suresh Jagannathan: I would classify the developments of the past decade into four broad categories:

  1. The development of higher-order recursion schemes (or higher-order model checking). This approach is based on defining a language semantics in terms of a (recursive) tree grammar. We can now ask whether the tree generated by the grammar satisfies a particular safety property. Because recursion schemes are very general and expressive structures, they can be viewed as natural extensions of model checkers based on pushdown automata or finite-state systems. In the past decade, there have been substantial advances that have made higher-order model checking a practical endeavor, accompanied by realistic implementations.
  2. Liquid Types combine facets of classic type inference techniques found in functional language with predicate abstraction techniques used in model checkers to automatically infer dependent type refinements with sufficient precision to prove useful safety properties about higher-order functional programs. Implementations of this approach found in OCaml, SML, and Haskell have demonstrated that it is indeed to possible to verify non-trivial program properties without significant type annotation burden.
  3. There have been substantial advances in the development of new languages built around rich dependent type systems that enable the expression and static verification of rich safety and security specifications and properties of higher-order programs. These include the languages that support mechanized proof assistants like Coq, Agda, or Epigram, languages like F* geared towards secure distributed programming, libraries like Ynot that encapsulate imperative (stateful) features and Hoare-logic pre/post-conditions within a higher-order dependent type framework, and features such as GADTs and type classes found in languages like GHC.
  4. Polyvariant control-flow analyses like CFA2 or higher-order contracts are two techniques that facilitate verification and analysis of dynamic higher-order languages. CFA2 adopts pushdown models used in program analyses for first-order languages to a higher-order setting, enabling precise matching of call/return sequences. Higher-order contracts allow runtime verification and blame assignment of higher-order programs and are fully incorporated into Racket, a multi-paradigm dialect of Lisp/Scheme.

Read more »

Ruediger Schack on quantum Bayesianism

 |   |  Conversations

Ruediger Schack portrait Ruediger Schack is a Professor at the Department of Mathematics at Royal Holloway, University of London. He obtained his PhD in Theoretical Physics at the University of Munich in 1991 and held postdoctoral positions at the Max Planck Institute for Quantum Optics, the University of Southern California, the University of New Mexico, and Queen Mary and Westfield College before joining Royal Holloway in 1995. His research interests are quantum information theory, quantum cryptography and quantum Bayesianism.

Luke Muehlhauser: In Fuchs et al. (2013), you and your co-authors provide an introduction to quantum Bayesianism aka “QBism,” which you more or less co-invented with Carlton Caves and Christopher Fuchs. But before I ask about QBism, let me ask one of the questions asked of the interviewees in Elegance and Enigma: The Quantum Interviews (including Fuchs): “What first stimulated your interest in the foundations of quantum mechanics?”


Ruediger Schack: I can trace the beginning of my interest in quantum foundations to reading one paper: “Where do we stand on maximum entropy?” by Ed Jaynes, and one book: Du Microscopique au Macroscopique by Roger Balian. Jaynes’s paper introduced me to Bayesian probability theory, and Balian’s book taught me that one can think of quantum states as representing Bayesian probabilities.

Read more »

David J. Atkinson on autonomous systems

 |   |  Conversations

David J. Atkinson portrait David J. Atkinson, Ph.D, is a Senior Research Scientist at the Florida Institute for Human and Machine Cognition (IHMC). His current area of research envisions future applications of intelligent, autonomous agents, perhaps embodied as robots, who work alongside humans as partners in teamwork or provide services. Dr. Atkinson’s major focus is on fostering appropriate reliance and interdependency between humans and agents, and the role of social interaction in building a foundation for mutual trust between humans and intelligent, autonomous agents. He is also interested in cognitive robotics, meta-reasoning, self-awareness, and affective computing. Previously, he held several positions at California Institute of Technology, JPL (a NASA Center), where his work spanned basic research in artificial intelligence, autonomous systems and robotics with applications to robotic spacecraft, control center automation, and science data analysis. Recently, Dr. Atkinson delivered an invited plenary lecture on the topic of “Trust Between Humans and Intelligent Autonomous Agents” at the 2013 IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT 2013). Dr. Atkinson holds a Bachelor’s degree in Psychology from University of Michigan, dual Master of Science and Master of Philosophy degrees in Computer Science (Artificial Intelligence) from Yale University, and the Doctor of Technology degree (d.Tekn) in Computer Systems Engineering from Chalmers University of Technology in Sweden.

Luke Muehlhauser: One of your projects at IHMC is “The Role of Benevolence in Trust of Autonomous Systems“:

The exponential combinatorial complexity of the near-infinite number of states possible in autonomous systems voids the applicability of traditional verification and validation techniques for complex systems. New and robust methods for assessing the trustworthiness of autonomous systems are urgently required if we are to have justifiable confidence in such applications both pre-deployment and during operations…  The major goal of the proposed research is to operationalize the concept of benevolence as it applies to the trustworthiness of an autonomous system…

Some common approaches for ensuring desirable behavior from AI systems include testing, formal methods, hybrid control, and simplex architectures. Where does your investigation of “benevolence” in autonomous systems fit into this landscape of models and methods?

Read more »

Help MIRI in a Massive 24-Hour Fundraiser on May 6th

 |   |  News

Update: We’re now liveblogging the fundraiser here.

On May 6th, MIRI is participating in Silicon Valley Gives. We were selected to participate along with other local Bay Area charities by the Silicon Valley Community Foundation. On this day, we recommend donors make gifts to MIRI through the SV Gives portal so we can qualify for some of the matching and bonus funds provided by dozens of Bay Area philanthropists.

Why is this exciting for supporters of MIRI? Many reasons, but here are a few:

  • Over $250,000 of matching funds and prizes up for grabs, from sources that normally wouldn’t contribute to MIRI:
    • Kick-off Match! Two-to-one dollar match up to $50,000 during the midnight hour.
    • $2,000 prize for the nonprofit that has the most individual donors in an hour, every hour for 24 hours.
    • Golden Ticket of $150 added to a random donation each hour, every hour, for 24 hours.
    • Dollar for Dollar match up to $35,000 during the 7 AM hour.
    • Dollar for Dollar match up to $15,000 during the 8 AM hour.
    • Dollar for Dollar match up to $50,000 during the 12 noon hour.
    • Dollar for Dollar match up to $50,000 during the 6 PM hour.
    • Dollar for Dollar match up to $50,000 during the 7 PM hour.
  • Local NBC stations, local radio stations, many local business, and lots of Bay Area foundations will be promoting the Silicon Valley Day of Giving on May 6th. So if MIRI is making a splash with our fundraising that day, it’s possible we’ll draw attention from media and by extension new donors.

We need your help to make the most of this opportunity!

Making the most of this opportunity will require some cleverness and a lot of coordination. We are going to need all the help we can get. Here are some ways you can help:

  1. We are currently thinking through how to best take advantage of  this unique opportunity. If you have any ideas and/or want to join the planning team (currently Malo, Louie, Luke, and long-time MIRI supporter Alexei Andreev), shoot Malo an email at malo@intelligence.org.
  2. If you are interested in supporting MIRI with a  donation of $500 or more during the fundraiser, we’d love to coordinate with you to make it count as much as possible. Get in touch with Malo at malo@intelligence.org.
  3. All MIRI supporters (not just donors) have the potential to make a big impact if we can all work together in a coordinated manner. Sign up below to receive updates on our strategy leading up to the event, and updates throughout the fundraiser on the best times to give and promote the event. Follow along with the excitement and be on the inside of what’s going on all day!

Roland Siegwart on autonomous mobile robots

 |   |  Conversations

Roland Siegwart portrait Roland Siegwart (born in 1959) is a Professor for Autonomous Systems and Vice President Research and Corporate Relations at ETH Zurich. After studying mechanics and mechatronics at ETH, he was engaged in starting up a spin-off company, spent ten years as professor for autonomous microsystems at EPFL Lausanne and held visiting positions at Stanford University and NASA Ames.

In his research interests are in the creation and control of intelligent robots operating in complex and highly dynamical environments. Prominent examples are personal and service robots, inspection devices, autonomous micro-aircrafts and walking robots. He is and was the coordinator of European projects, co-founder of half a dozen spin-off companies and board member of various high-tech companies.

Roland Siegwart is member of the Swiss Academy of Engineering Sciences, IEEE Fellow and officer of the International Federation of Robotics Research (IFRR). He is in the editorial board of multiple journals in robotics and was a general chair of several conferences in robotics including IROS 2002, AIM 2007, FSR 2007, ISRR 2009.

Luke Muehlhauser: In 2004 you co-authored Introduction to Autonomous Mobile Robots, which offers tutorials on many of the basic tasks of autonomous mobile robots: locomotion, kinematics, perception, localization, navigation, and planning.

In your estimation, what are the most common approaches to “gluing” these functions together? E.g. are most autonomous mobile robots designed using an agent architecture, or some other kind of architecture?


Roland Siegwart: Mobile robots are very complex systems, that have to operate in real world environments and have to take decisions based on uncertain and only partially available information. In order to do so, the robot’s locomotion, perception and navigation system has to be best adapted to the environment and application setting. So robotics is before all a systems engineering task requiring a broad knowledge and creativity. A wrongly chosen sensor setup cannot be compensated by the control algorithms. In my view, the only proven concepts for autonomous decision making with mobile robots are Gaussian Processes and Bayes Filters. They allow to deal with uncertain and partial information in a consistent way and enable learning. Gaussian Processes and Bayes filter can model a large variety of estimation and decision processes and can be implemented in different forms, e.g. as the well-known Kalman Filter estimator.

Most mobile robots use some sort of agent architecture. However, this is not a key issue in mobile robots, but rather an implementation issue for systems that run multiple tasks in parallel. The main perception, navigation and control algorithms have to adapt to unknown situation in a somewhat predictably and consistent manner. Therefore the algorithms and navigation concepts should also allow the robotics engineer to learn from experiments. This is only possible, if navigation, control and decision making is not implemented in a black-box manner, but in a model based approach taking best advantage of prior knowledge and systems models.
Read more »

Domitilla del Vecchio on hybrid control for autonomous vehicles

 |   |  Conversations

Domitilla Del Vecchio portrait Domitilla Del Vecchio received the Ph. D. degree in Control and Dynamical Systems from the California Institute of Technology, Pasadena, and the Laurea degree in Electrical Engineering from the University of Rome at Tor Vergata in 2005 and 1999, respectively. From 2006 to 2010, she was an Assistant Professor in the Department of Electrical Engineering and Computer Science and in the Center for Computational Medicine and Bioinformatics at the University of Michigan, Ann Arbor. In 2010, she joined the Department of Mechanical Engineering and the Laboratory for Information and Decision Systems (LIDS) at the Massachusetts Institute of Technology (MIT), where she is currently an Associate Professor. She is a recipient of the Donald P. Eckman Award from the American Automatic Control Council (2010), the NSF Career Award (2007), the Crosby Award, University of Michigan (2007), the American Control Conference Best Student Paper Award (2004), and the Bank of Italy Fellowship (2000). Her research interests include analysis and control of networked dynamical systems with application to bio-molecular networks and transportation networks.

Luke Muehlhauser: In Verma & del Vecchio (2011), you and your co-author summarize some recent work in semiautonomous multivehicle safety from the perspective of hybrid systems control. These control systems will “warn the driver about incoming collisions, suggest safe actions, and ultimately take control of the vehicle to prevent an otherwise certain collision.”

I’d like to ask about the application of hybrid control to self-driving cars in particular. Presumably, self-driving cars will operate in two modes: “semi-autonomous” (human driver, with the vehicle providing warnings and preventing some actions) and “fully autonomous” (no human driver). Do you think hybrid control will be used for both purposes, in commercial self-driving cars released (e.g.) 10 years from now? Or do you think hybrid control will be competing with other approaches aimed at ensuring safe behavior in autonomous and semi-autonomous vehicles?

Read more »

Dave Doty on algorithmic self-assembly

 |   |  Conversations

Dave Doty portrait Dave Doty is a Senior Research Fellow at the California Institute of Technology. He proves theorems about molecular computing and conducts experiments implementing algorithmic molecular self-assembly with DNA.

 

 

 

 

Luke Muehlhauser: A couple years ago you wrote a review article on algorithmic self-assembly, and also created a video introduction to the subject. Your review article begins:

Self-assembly is the process by which small components automatically assemble themselves into large, complex structures. Examples in nature abound: lipids self-assemble a cell’s membrane, and bacteriophage virus proteins self-assemble a capsid that allows the virus to invade other bacteria. Even a phenomenon as simple as crystal formation is a process of self-assembly… Algorithmic self-assembly systems automate a series of simple growth tasks, in which the object being grown is simultaneously the machine controlling its own growth.

As an example, here’s a an electron microscope image of a Sierpinski triangle produced via algorithmic self-assembly of DNA molecules:

Read more »

Ariel Procaccia on economics and computation

 |   |  Conversations

Ariel Procaccia portrait Ariel Procaccia is an assistant professor in the Computer Science Department at Carnegie Mellon University. He received his Ph.D. in computer science from the Hebrew University of Jerusalem. He is a recipient of the NSF CAREER Award (2014), the (inaugural) Yahoo! Academic Career Enhancement Award (2011), the Victor Lesser Distinguished Dissertation Award (2009), and the Rothschild postdoctoral fellowship (2009). Procaccia was named in 2013 by IEEE Intelligent Systems to their biennial list of AI’s 10 to Watch. He is currently the editor of ACM SIGecom Exchanges, an associate editor of the Journal of AI Research (JAIR) and Autonomous Agents and Multi-Agent Systems (JAAMAS), and an editor of the upcoming Handbook of Computational Social Choice.

Read more »

As featured in:     Forbes   MSNBC   Popular Science   SF Weekly   WIRED