MIUR PRIN PROJECT

MIUR PRIN PROJECT “APPROCCI INNOVATIVI E MULTI-­‐
DISCIPLINARI PER RAGIONAMENTO CON VINCOLI E PREFERENZE” Francesca Rossi University of Padova Perugia, 12.9.2011 Aula seminari Dipar@mento Matema@ca e Informa@ca Research units • 
• 
• 
• 
• 
University of Padova (Rossi) University of Udine (Dovier) University of Bologna (Gabbrielli) University of Perugia (Bistarelli) CNR-­‐ISTI Roma (Cesta) Timing •  March 2010 to September 2012 Already 1 year and 6 months aOer beginning of project (more than half) Objec@ves (in the proposal) • 
Constraints and preferences – 
– 
– 
– 
– 
– 
• 
Constraint-­‐based programming languages – 
– 
– 
• 
Uncertainty, controllability Space applica@ons, assis@ve technology Mul@-­‐agent preference reasoning – 
– 
– 
– 
• 
CLP, CC, ASP CC + soO/temporal constraints + stochas@c features Program transforma@on, automated verifica@on, synthesis Temporal reasoning – 
– 
• 
Unifying framework Uncertainty Global constraints Local search Biology problems Generic constraint solver cp+ls Preference gaggrega@on Uncertainty Computa@onal proper@es Stable matching Applica@ons – 
– 
– 
– 
COLA for biology CC+temporal logics for biology SoO connsraints for QoS TRF plaYorm for planning and scheduling Padova unit • 
• 
• 
• 
Francesca Rossi (professor, unit leader) Kristen Brent Venable (assistant professor) Maria Silvia Pini (FSE post-­‐doc researcher) Mirco Gelain (PhD student un@l December 2010) Uncertainty in soO constraint problems • 
• 
• 
• 
• 
Elicita@on Strategies for SoO Constraint Problems with Missing Preferences: Proper@es, Algorithms and Experimental Studies, Mirco Gelain, Maria Silvia Pini, Francesca Rossi, K. Brent Venable, Toby Walsh, Ar@ficial Intelligence Journal, volume 174, pp. 270-­‐294, 2010. SoO Constraint Problems With Uncontrollable Variables, Maria Silvia Pini, Francesca Rossi, K. Brent Venable, Journal of Experimental & Theore@cal Ar@ficial Intelligence (JETAI), Volume 22 Issue 4, page 269, 2010. Interval-­‐valued SoO Constraint Problems, M. Gelain, M. S. Pini, F. Rossi, K. B. Venable, and N. Wilson, Annals of Mathema@cs and Ar@ficial Intelligence, special issue for ISAIM 2008, B. Chouery and B. Givan eds., Volume 58, Issue 3, page 261, 2010. Uncertainty in Bipolar Preference Problems, S, Bistarelli, M, S, Pini, F. Rossi and K. Brent Venable, Journal of Experimental & Theore@cal Ar@ficial Intelligence (JETAI), to appear. A local search approach to solve incomplete fuzzy CSPs, Mirco Gelain, Maria Silvia Pini, Francesca Rossi, K. Brent Venable, Toby Walsh, Proc. ICAART 2011. Next solu@on in preference problems •  Finding the next solu@on in constraint-­‐ and preference-­‐based knowledge representa@on formalisms, Ronen Brafman Francesca Rossi, Domenico Salvagnin, Brent Venable, Toby Walsh, Proc. KR 2010, Toronto, Canada, May 9-­‐13, 2010. •  The next best solu@on, Ronen Brafman, Enrico Piloho, Francesca Rossi, Domenico Salvagnin, K. Brent Venable, Toby Walsh, Proc. AAAI 2011 NECTAR track. Mul@-­‐agent preference systems • 
• 
• 
• 
• 
• 
Incompleteness and Incomparability in Preference Aggrega@on: Complexity Results, M.S. Pini, F. Rossi, K. Venable, T.Walsh, Ar@ficial Intelligence Journal, special issue on "Represen@ng, Processing, and Learning Preferences: Theore@cal and Prac@cal Challenges", C. Domshlak, E. Hollermeier, S. Kaci, H. Prade, eds., volume 175, Issues 7-­‐8, May 2011, Pages 1272-­‐1289. Mul@-­‐agent soO constraint aggrega@on: a sequen@al approach, Giorgio Dalla Pozza, Francesca Rossi, K. Brent Venable, Proc. ICAART 2011. Possible and necessary winners in vo@ng trees: majority graphs vs. profiles, Maria Silvia Pini, Francesca Rossi, K. Brent Venable, Toby Walsh, Proc. AAMAS 2011. Winner determina@on in vo@ng trees with incomplete preferences and weighted votes, Jerome Lang, Maria Silvia Pini, Francesca Rossi, Domenico Salvagnin, K. Brent Venable, Toby Walsh, to appear in Journal of Autonomous Agents and Mul@-­‐Agent Systems. Mul@-­‐agent soO constraint aggrega@on via sequen@al vo@ng, Giorgio Dalla Pozza, Maria Silvia Pini, Francesca Rossi, K. Brent Venable, Proc. IJCAI 2011. Influencing and aggrega@ng agents' preferences over combinatorial domains, Nicola Maudet, Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable, Proc. IJCAI 2011 workshop on social choice and AI, Barcelona, July 2011. Stable matching problems • 
• 
• 
• 
• 
• 
• 
• 
Male op@mality and uniqueness in stable matching problems with par@al orders, Maria Silvia Pini, Francesca Rossi, Toby Walsh, Mirco Gelain, Kristen Brent Venable, Proc. AAMAS 2010, Toronto, Canada, May 10-­‐14, 2010. Local search for stable marriage problems with @es and incomplete lists, M. Gelain, M. S. Pini, F. Rossi, K. B. Venable, T. Walsh, Proc. PRICAI 2010 (11th Pacific Rim Interna@onal Conference on Ar@ficial Intelligence), Byoung-­‐Tak Zhang and Mehmet A. Orgun eds., Springer LNAI 6230, 2010. Local search algorithms on the Stable Marriage Problem: Experimental Studies, M. Gelain, M. S. Pini, F. Rossi, K. B. Venable, T. Walsh, Proc. ECAI 2010, Lisbon, Portugal, August 16-­‐20, 2010. Male op@mal and unique stable marriages with par@ally ordered preferences, Mirco Gelain, Maria Silvia Pini, Francesca Rossi, K. Brent Venable, Toby Walsh, post-­‐proceedings Interna@onal Workshop on Collabora@ve Agents -­‐ REsearch and development (CARE 2009/2010), LNAI 6066, Springer, 2010, Chris@an Guhmann, Frank Dignum, Michael Georgeff eds. Manipula@on complexity and gender neutrality in stable marriage procedures, Maria Silvia Pini, Francesca Rossi, K. Brent Venable, Toby Walsh, Journal of Autonomous Agents and Mul@-­‐Agent Systems, Volume 22, Issue 1, p. 183, 2011. Stability in matching problems with weighted preferences, Maria Silvia Pini, Francesca Rossi, K. Brent Venable, Toby Walsh, Proc. ICAART 2011. Procedural fairness in stable marriage problems, Mirco Gelain, Maria Silvia Pini, Francesca Rossi, K. Brent Venable, Toby Walsh, Proc. AAMAS 2011. Weights in stable marriage problems increase manipula@on opportuni@es, Maria Silvia Pini, Francesca Rossi, Kristen Brent Venable, Toby Walsh, Proc. TARK 2011. Doodle •  To decide the @me of a mee@ng •  Several @me slots are given to the par@cipants •  Each par@cipant can either accept or reject each @me slot •  The chosen @me slot is the one with greatest number of acceptances Preference-­‐based Doodle Four modes: 1.  Same as Doodle: accept/reject 2.  Each par@cipant may reject some @meslots and ranks the other ones –  Ranks are transformed into points •  If there are 10 @me slots and only three are accepted, 1,2,3 becomes 10,9,8 –  Winner @me slot: •  Largest number of acceptances •  Largest number of points Preference-­‐based Doodle •  Each par@cipant may reject some @meslots and has 100 points to distribute to the other ones 1.  Score for a @me slot: sum of points received •  Winner @me slot: –  Largest number of acceptances –  Maximum score (we maximize the sum of points received by all par@cipants) 2.  Score for a @me slot: minimum of points received •  Winner @me slot: –  Largest number of acceptances –  Maximum score (we maximize the happiness of the less happy par@cipant) •  hhp://[email protected]/ Timeslot defini@on Home Home 1 Home 2 Timeslot defini@on Accept/reject Timeslot ranking Point distribu@on