In this paper, we present a planning and control framework for dynamic, wholebody motions for dynamically stable shapeaccelerating mobile manipulators. This class of robots are inherently unstable and require careful coordination between the upper and lower body to maintain balance while performing manipulation tasks. Solutions to this problem either use a complex, fullbody nonlinear dynamic model of the robot or a highly simplified model of the robot. Here we explore the use of centroidal dynamics which has recently become a popular approach for designing balancing controllers for humanoid robots. We describe a framework where we first solve a trajectory optimizationmore »
This content will become publicly available on May 6, 2023
Proactive Dynamic Distributed Constraint Optimization Problems
The Distributed Constraint Optimization Problem (DCOP) formulation is a powerful tool for modeling multiagent coordination problems. To solve DCOPs in a dynamic environment, Dynamic DCOPs (DDCOPs) have been proposed to model the inherent dynamism present in many coordination problems. DDCOPs solve a sequence of static problems by reacting to changes in the environment as the agents observe them. Such reactive approaches ignore knowledge about future changes of the problem. To overcome this limitation, we introduce Proactive Dynamic DCOPs (PDDCOPs), a novel formalism to model DDCOPs in the presence of exogenous uncertainty. In contrast to reactive approaches, PDDCOPs are able to explicitly model possible changes of the problem and take such information into account when solving the dynamically changing problem in a proactive manner. The additional expressivity of this formalism allows it to model a wider variety of distributed optimization problems. Our work presents both theoretical and practical contributions that advance current dynamic DCOP models: (i) We introduce Proactive Dynamic DCOPs (PDDCOPs), which explicitly model how the DCOP will change over time; (ii) We develop exact and heuristic algorithms to solve PDDCOPs in a proactive manner; (iii) We provide theoretical results about the complexity of this new class of DCOPs; and more »
 Award ID(s):
 2143706
 Publication Date:
 NSFPAR ID:
 10337587
 Journal Name:
 Journal of Artificial Intelligence Research
 Volume:
 74
 Page Range or eLocationID:
 179 to 225
 ISSN:
 10769757
 Sponsoring Org:
 National Science Foundation
More Like this


We consider the communication complexity of a number of distributed optimization problems. We start with the problem of solving a linear system. Suppose there is a coordinator together with s servers P1, …, Ps, the ith of which holds a subset A(i) x = b(i) of ni constraints of a linear system in d variables, and the coordinator would like to output an x ϵ ℝd for which A(i) x = b(i) for i = 1, …, s. We assume each coefficient of each constraint is specified using L bits. We first resolve the randomized and deterministic communication complexity inmore »

Applications in environmental monitoring, surveillance and patrolling typically require a network of mobile agents to collectively gain information regarding the state of a static or dynamical process evolving over a region. However, these networks of mobile agents also introduce various challenges, including intermittent observations of the dynamical process, loss of communication links due to mobility and packet drops, and the potential for malicious or faulty behavior by some of the agents. The main contribution of this paper is the development of resilient, fullydistributed, and provably correct state estimation algorithms that simultaneously account for each of the above considerations, and inmore »

We study the communication cost (or message complexity) of fundamental distributed symmetry breaking problems, namely, coloring and MIS. While significant progress has been made in understanding and improving the running time of such problems, much less is known about the message complexity of these problems. In fact, all known algorithms need at least Ω(m) communication for these problems, where m is the number of edges in the graph. We addressthe following question in this paper: can we solve problems such as coloring and MIS using sublinear, i.e., o(m) communication, and if sounder what conditions? In a classical result, Awerbuch, Goldreich,more »

With the rapid growth of online social media and ubiquitous Internet connectivity, social sensing has emerged as a new crowdsourcing application paradigm of collecting observations (often called claims) about the physical environment from humans or devices on their behalf. A fundamental problem in social sensing applications lies in effectively ascertaining the correctness of claims and the reliability of data sources without knowing either of them a priori, which is referred to as truth discovery. While significant progress has been made to solve the truth discovery problem, some important challenges have not been well addressed yet. First, existing truth discovery solutionsmore »