What Determines Difficulty of Transport Puzzles?

PELÁNEK, Radek and Petr JARUŠEK. What Determines Difficulty of Transport Puzzles? In Philip M. McCarthy, R. Charles Murray. Twenty-Fourth International Florida Artificial Intelligence Research Society Conference. USA: Association for the Advancement of Artificial Intelligence (AAAI), 2011, p. 428-433. ISBN 978-1-57735-501-4.

Basic information

• Original name: What Determines Difficulty of Transport Puzzles?
• Name in Czech: Co určuje obtížnost transportních úloh?
• Authors: PELÁNEK, Radek (203 Czech Republic, guarantor, belonging to the institution) and Petr JARUŠEK (203 Czech Republic, belonging to the institution).
• Edition: USA, Twenty-Fourth International Florida Artificial Intelligence Research Society Conference, p. 428-433, 6 pp. 2011.
• Publisher: Association for the Advancement of Artificial Intelligence (AAAI)

Other information

• Original language: English
• Type of outcome: Proceedings paper
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: United States of America
• Confidentiality degree: is not subject to a state or trade secret
• RIV identification code: RIV/00216224:14330/11:00049813
• Organization unit: Faculty of Informatics
• ISBN: 978-1-57735-501-4
• Keywords (in Czech): výpočetní model; řešení problémů; Sokoban; stavové prostory; obtížnost; experimentální vyhodnocení
• Keywords in English: computational model; human problem solving; transport puzzles; Sokoban; state spaces; difficulty; evaluation
• Tags: International impact, Reviewed

Abstract

What determines difficulty of solving a problem? Although this question has been studied before, we found examples which show large differences in problem difficulty which are not explained by concepts identified in previous research. This differences are caused mainly by the structure of a problems' state spaces and cannot be easily captured by static metrics like size of the state space or the length of a solution. To address these unexplained differences, we propose a computational model of human problem solving behaviour. We provide evaluation of the model over large scale dataset (hundreds of hours of problem solving, more than 100 problem instances) for three transport puzzles (Sokoban, Rush hour, and Replacement puzzle).

Links

• GAP202/10/0334, research and development project: Name: Řešení obtížných dobře strukturovaných problémů: spolupráce člověka a počítače

Investor: Czech Science Foundation

• MUNI/A/0914/2009, interní kód MU: Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace (Acronym: SV-FI MAV)

Investor: Masaryk University, Category A

• 1M0545, research and development project: Name: Institut Teoretické Informatiky

Investor: Ministry of Education, Youth and Sports of the CR, Institute for Theoretical Computer Science