Research

Social Mini-Games

Three social mini-games Three social mini-games side by side: a doorway, a corridor, and an intersection. In each one, two robots approach a shared piece of space that only one of them can use at a time, and their paths conflict. doorway corridor intersection

A social mini-game (SMG) is a short, local interaction in a physically constrained environment in which a few agents (robots and/or humans) compete for a shared space that only one of them can use at a time (e.g. going through doorways, narrow hallways, unsignalized intersections etc.). SMGs exhibit high agency where small actions can significantly change the interaction dynamics, coordination requirements, and potential for deadlocks.

SMGs can be formalized as a multi-agent variation of a spatially constrained, time-optimal, motion planning problem in which a frequent failure mode is the freezing robot problem in which robots stop moving because every available motion looks unsafe.

Humans solve SMGs quickly, without speaking and usually without slowing down much. We want robots to do the same, and we want to be able to prove that they will.

This paper introduces the SMG problem and puts it in context with the broader literature on multi-robot navigation. The following are some exciting open problems in robotics and autonomy towards solving SMGs:

  1. What sort of guarantees can we give to SMG solvers? e.g. safety? goal-reaching (task completion)? realtime? min-time? robustness/generalizability? scalability? And to what extent do we need to relax the taxonomy/assumptions to ensure these guarantees?
  2. What role does physical AI play in solving SMGs and how do we integrate reasoning and classical control-theoretic approaches in a closed-loop feedback mechanism, especially when solving SMGs with underactuated systems like humanoid robots?
  3. What does it take to solve SMGs that involve humans? How can SMG solvers take human irrationality into account? Also, how do we trade off between social compliance and safety around humans?
  4. Is there a unifying connection between different approaches to solving SMGs? for example, can MARL, MAPF, dynamic game theory, and trajectory optimization be reduced to a “master” algorithm?
01

AI

02

Planning

03

Control

04

Datasets, Simulators, and Surveys