A problem-decomposition method using differences or equivalence relations between states

DOI10.1016/0004-3702(85)90001-3MaRDI QIDQ1058310zbMATH OpenOpenAlexFDO

Authors Seizaburo Niizuma, Tadahiro Kitahashi

Publication date 1985

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0004-3702(85)90001-3

zbMATH Keywords

ABSTRIPSGPSplanningproblem decomposition

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Review text

The mathematical model of representing a problem by a set S of states together with partial transition functions (means) is adopted. States are endowed with certain features which give rise to equivalence relations on S, the complements of which are called differences on S. A method for decomposing a problem into simpler subproblems is proposed and conditions under which this leads to success are given. The concepts and the method are amply illustrated by analysing the 3-tower of Hanoi game and the 5- puzzle. The method is compared with Ernst and Newell's GPS and Sacerdoti's ABSTRIPS.

Recommendations

• scientific article; zbMATH DE number 3858935
• A state polytope decomposition formula
• scientific article; zbMATH DE number 4045654
• Publication:4725760
• Decomposition method of solving a class of combinatorial optimization problems
• scientific article; zbMATH DE number 4011870
• Boolean valued decomposition theory of states
• Equivalences of Statecharts
• A graph-theoretical characterisation of state separation

Cites work

• scientific article; zbMATH DE number 3298341 (Why is no real title available?)
• scientific article; zbMATH DE number 3309664 (Why is no real title available?)
• scientific article; zbMATH DE number 3319498 (Why is no real title available?)
• Mechanical Discovery of Classes of Problem-Solving Strategies
• Planning in a hierarchy of abstraction spaces
• Realization theory of continuous-time dynamical systems
• Sufficient Conditions for the Success of GPS

Cited in

(6)

• An optimal algorithm for Reve's puzzle
• Shortest paths between regular states of the Tower of Hanoi
• Parallelism for multipeg towers of Hanoi
• Formulating patterns in problem solving
• scientific article; zbMATH DE number 4076680 (Why is no real title available?)
• A systematic solution to the (de-)composition problem in general game playing

This page was built for publication: A problem-decomposition method using differences or equivalence relations between states

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1058310)