Short Term Scientific Mission, COST Action IC0602
Beneficiary: PALACIOS Hector, Universidad Carlos III
Host: Jerome Lang, LAMSADE, Univ. Paris Dauphine.
Period: from 21/03/2011 to 02/04/2011
Place: Paris (France)
Reference code: ECOST-STSM-IC0602-210311-006813-6813

In the short visit of Hector Palacios to Jerome Lang, in Paris, from 21
Feb. to 2 April, 2011, we investigate on new connections between
Computational Social Choice and Planning.

We focused on the problem of Group Planning, where agents decide
together to execute an action, but they differ on which goal they prefer
to achieve. There is related work on agents deciding what actions/edge
to follow in a graph, but such work focus on finding a hamiltonian path
or spanning trees. However, we are not aware of considering the same
situation on a general planning setting.

One of the main difficulties is to determine whether an state is
reachable by a plan or not, a problem that is PSPACE-complete in the
general case. A naive approach would be to calculate the set of
reachable states and then ask the voters for the ranking among those
reachable actions.

For avoiding such expensive step, we are considering some
approximations. One possibility if to calculate a full rank over the goal
states, and then report as a winner the most preferred feasible goal.
Other option is to calculate the winner, and try to achieve it.
Otherwise, remove such state as a candidate and calculate the winner
again. We want to study such options in the context of specific voting
rules, to assess its behaviour in comparison with the optimal but
expensive approach.

I have also the opportunity of talking with Craig Boutilier, who was
visiting Jerome in Paris. He also discussed with us about group planning
among other topics.