Opportunistic Hit-or-Wait

Opportunistic Hit-or-Wait

Figure: Illustration of the search distribution coverage across task delivery mechanisms for on-the-go crowds. Tall black bars denote wasted effort; gray boxes denote missed opportunities. The Hit-or-Wait algorithm achieves a near-optimal distribution across all areas that need to be searched, without affecting people’s routes.

We consider the challenge of deciding whether to send a task that is near the helper now— which we call hitting—or to wait for a better opportunity. This challenge follows from a general goal of physical tasking systems to efficiently leverage helper efforts where they are most needed, and to keep the cost of disruption low by not inundating a helper with notifications of task opportunities. In practice, there may be many tasks a person can contribute to during their routine, and deciding which task to notify them about indirectly affects where contributions are made, what tasks are ignored, and what outcomes are prioritized. Our goal is to be able to intelligently control decisions over when to notify a person of a task, in ways that can reason both about system needs and about a helper’s changing patterns of mobility.

Seemingly reasonable system decisions on whether and when to notify helpers of tasks can have numerous unintended consequences in practice due to timing issues and characteristics of mobility patterns. For example, we may wait for the best match of a helper to a task (e.g., where they are competent, face low costs of diversion, for a high value, high priority task), only to find that the person never came near that task location in their realized routes. We can also be overly opportunistic, sending a person the first task they come in contact with, only to realize that adopting this strategy leads to certain tasks or physical regions being overly well-represented while other tasks or regions are never completed or reached.

Sprint Video



  • Haoqi Zhang

Ph.D. Students

  • 🎓 Yongsung Kim

Masters and Undergraduate Students

  • None