Unmanned deep-sea and planetary vehicles operate in highly uncertain environments. Autonomous agents often are not adopted in these domains due to the risk of mission failure, and loss of vehicles. Prior work on contingent plan execution addresses this issue by placing bounds on uncertain variables and by providing consistency guarantees for a `worst-case' analysis, which tends to be too conservative for real-world applications. In this work, we unify features from trajectory optimization through risk-sensitive execution methods and high-level, contingent plan execution in order to extend existing guarantees of consistency for conditional plans to a chance-constrained setting. The result is a set of efficient algorithms for computing plan execution policies with explicit bounds on the risk of failure. To accomplish this, we introduce Probabilistic Temporal Plan Network (pTPN), which improve previous formulations, by incorporating probabilistic uncertainty and chance-constraints into the plan representation. We then introduce a novel method to the chance-constrained strong consistency problem, by leveraging a conflict-directed approach that searches for an execution policy that maximizes reward while meeting the risk constraint. Experimental results indicate that our approach for computing strongly consistent policies has an average scalability gain of about one order of magnitude, when compared to current methods based on chronological search.
In this paper, we propose a comprehensive study of second-order consistencies (i.e., consistencies identifying inconsistent pairs of values) for constraint satisfaction. We build a full picture of the relationships existing between four basic second-order consistencies, namely path consistency (PC), 3-consistency (3C), dual consistency (DC) and 2-singleton arc consistency (2SAC), as well as their conservative and strong variants. Interestingly, dual consistency is an original property that can be established by using the outcome of the enforcement of generalized arc consistency (GAC), which makes it rather easy to obtain since constraint solvers typically maintain GAC during search. On binary constraint networks, DC is equivalent to PC, but its restriction to existing constraints, called conservative dual consistency (CDC), is strictly stronger than traditional conservative consistencies derived from path consistency, namely partial path consistency (PPC) and conservative path consistency (CPC). After introducing a general algorithm to enforce strong (C)DC, we present the results of an experimentation over a wide range of benchmarks that demonstrate the interest of (conservative) dual consistency. In particular, we show that enforcing (C)DC before search clearly improves the performance of MAC (the algorithm that maintains GAC during search) on several binary and non-binary structured problems.
Enforcing local consistencies is one of the main features of constraint reasoning. Which level of local consistency should be used when searching for solutions in a constraint network is a basic question. Arc consistency and partial forms of arc consistency have been widely studied, and have been known for sometime through the forward checking or the MAC search algorithms. Until recently, stronger forms of local consistency remained limited to those that change the structure of the constraint graph, and thus, could not be used in practice, especially on large networks. This paper focuses on the local consistencies that are stronger than arc consistency, without changing the structure of the network, i.e., only removing inconsistent values from the domains. In the last five years, several such local consistencies have been proposed by us or by others. We make an overview of all of them, and highlight some relations between them. We compare them both theoretically and experimentally, considering their pruning efficiency and the time required to enforce them.
Mobile robots moving in a crowd need to conform to the same social standards as the human participants. Imitating human behavior is a natural choice in these situations — however, not every human behaves in the same way. On the other hand, it is known that humans tend to behave in a consistent way, with their behavior predictable by their social status. In this paper we consider a marketplace where humans perform purposeful movement. With many people moving on intersecting trajectories, the participants occasionally encounter em micro-conflicts, where they need to balance their desire to move towards their destination (their mission) with the requirements of the social norms of not bumping into strangers or violating their personal space. We model micro-conflicts by a series of two-player games. We show that if all humans are using consistent strategies which are aware of their own social status and can infer the social status of their opponent, the overall social costs will be lower compared to scenarios where the humans perform inconsistent strategies (even if those strategies are adaptive). We argue that robots acting in social environments should also adopt consistent strategies and align themselves with the ongoing social structure.