Two AAAI-07 talks
Date: Thursday, July 5th
Time: 11-12pm
Room: PT266
Using Expectation Maximization to Find Likely Assignments for Constraint Satisfaction Problems
by Eric Hsu, Matthew Kitching, Fahiem Bacchus, Sheila McIlraith
(Speaker: Eric Hsu)
A Logical Theory of Coordination and Joint Ability
by Hojjat Ghaderi
Using Expectation Maximization to Find Likely Assignments for Constraint Satisfaction Problems
by Eric Hsu, Matthew Kitching, Fahiem Bacchus, Sheila McIlraith
Abstract:
We present a new probabilistic framework for finding likely variable assignments in difficult constraint satisfaction problems. Finding such assignments is key to efficient search, but practical efforts have largely been limited to random guessing and heuristically designed weighting systems. In constrast, we derive a new version of Belief Propagation (BP) using the method of Expectation Maximization (EM). This allows us to differentiate between variables that are strongly biased toward particular values and those that are essentially extraneous. Using EM also eliminates the threat of nonconvergence associated with regular BP. Theoretically, the derivation exhibits appealing primal/dual semantics. Empirically, it produces an EMBP-based heuristic that outperforms existing techniques for guiding variable and value ordering during backtracking search.
A Logical Theory of Coordination and Joint Ability
by Hojjat Ghaderi
Abstract:
A team of agents is jointly able to achieve a goal if despite any incomplete knowledge they may have about the world or each other, they still know enough to be able to get to a goal state. Unlike in the single-agent case, the mere existence of a working plan is not enough as there may be several incompatible working plans and the agents may not beable to choose a share that coordinates with those of the others. Some formalizations of joint ability ignore this issue of coordination within a coalition. Others, including those based on game theory, deal with coordination, but require a complete specification of what the agents believe. Such a complete specification is often not available. Here we present a new formalization of joint ability based on logical entailment in the situation calculus that avoids both of these pitfalls.
