Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2015 | Buch

An Overview of Picat Kapitel lesen Erstes Kapitel lesen

Constraint Solving and Planning with Picat

verfasst von: Neng-Fa Zhou, Håkan Kjellerstrand, Jonathan Fruhman

Verlag: Springer International Publishing

Buchreihe : SpringerBriefs in Intelligent Systems

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

This book introduces a new logic-based multi-paradigm programming language that integrates logic programming, functional programming, dynamic programming with tabling, and scripting, for use in solving combinatorial search problems, including CP, SAT, and MIP (mixed integer programming) based solver modules, and a module for planning that is implemented using tabling.

The book is useful for undergraduate and graduate students, researchers, and practitioners.

Inhaltsverzeichnis

Frontmatter
Chapter 1. An Overview of Picat
Abstract
Picat is a general-purpose programming language that includes features from multiple programming paradigms. By combining imperative programming’s control flow features with more advanced features from logic programming, functional programming, and scripting, Picat provides users a wide array of tools for efficiently creating programs to solve problems. A comparison with other programming languages shows how Picat programs can be more compact, more intuitive, and easier to read.
Neng-Fa Zhou, Håkan Kjellerstrand, Jonathan Fruhman
Chapter 2. Basic Constraint Modeling
Abstract
Given a set of variables, each of which has a domain of possible values, and a set of constraints that limit the acceptable set of assignments of values to variables, the goal of a CSP (Constraint Satisfaction Problem) is to find an assignment of values to the variables that satisfies all of the constraints. Picat provides three solver modules, including cp (Constraint Programming), sat (Satisfiability), and mip (Mixed Integer Programming), for modeling and solving CSPs. This chapter provides an introduction to modeling with constraints, with a primary focus on the cp module, and a secondary focus on the sat and mip modules.
Neng-Fa Zhou, Håkan Kjellerstrand, Jonathan Fruhman
Chapter 3. Advanced Constraint Modeling
Abstract
This chapter describes more advanced techniques of constraint modeling in Picat, as well as some tips about performance and debugging. The Langford number problem shows the use of the global constraint element and the concepts of reversibility and symmetry breaking. Reification, or reasoning about constraints, is exemplified with a decomposition of all_different_except_0, as well as the Who Killed Agatha problem. A separate section describes the importance of declaring domains to be as small as possible (but not smaller). This is followed by a section about search strategies, in which the magic squares problem is used for systematically testing many search strategies. The cumulative constraint is used for scheduling furniture moving, including precedences. Then, the magic sequences problem shows how to use the global constraint global_cardinality, and explains that the order of constraints in a model might matter. The circuit constraint is used for modeling the knight’s tour problem. The regular constraint, defined by a Deterministic Finite Automaton, is used in two models, first for a decomposition of the global_contiguity constraint, and then for modeling a nurse rostering problem. This is followed by an alternative approach of the nurse rostering problem that uses the table_in constraint. The chapter ends with some general tips about how to debug constraint models, when the models don’t give a solution, or when the solution is not correct.
Neng-Fa Zhou, Håkan Kjellerstrand, Jonathan Fruhman
Chapter 4. Dynamic Programming with Tabling
Abstract
Tabling is a kind of memoization technique that caches the results of certain calculations in memory and reuses them in subsequent calculations through a quick table lookup. Tabling makes declarative dynamic programming possible. Users only need to describe how to break a problem into subproblems; they do not need to implement the data structures and algorithms for storing and looking up subproblems and their answers. This chapter describes the syntax and semantics of tabling in Picat, and demonstrates several dynamic programming examples.
Neng-Fa Zhou, Håkan Kjellerstrand, Jonathan Fruhman
Chapter 5. From Dynamic Programming to Planning
Abstract
Planning can be treated as dynamic programming, for which tabling has been shown to be effective. Picat provides a module, named planner, which is based on tabling, but provides a level of abstraction that hides tabling from users. This chapter focuses on depth-unbounded search predicates in the planner module, and demonstrates several application examples.
Neng-Fa Zhou, Håkan Kjellerstrand, Jonathan Fruhman
Chapter 6. Planning with Resource-Bounded Search
Abstract
In addition to depth-unbounded search predicates, Picat’s planner also provides resource-bounded search predicates. Resource-bounded search amounts to utilizing tabled states and their resource amounts to effectively decide when a state should be expanded and when a state should fail. Picat’s planner provides iterative-deepening and branch-and-bound search predicates for finding optimal plans. Picat’s planner also supports heuristic search. A state should fail if its heuristic estimate of the cost to reach a final state is greater than its resource amount. This chapter describes resource-bounded search predicates in the planner module, and demonstrates several application examples.
Neng-Fa Zhou, Håkan Kjellerstrand, Jonathan Fruhman
Chapter 7. Encodings for the Traveling Salesman Problem
Abstract
So far, this book has presented several techniques for modeling constraint satisfaction, dynamic programming, and planning problems. This chapter presents encodings for the Traveling Salesman Problem, comparing models for several solvers, including CP, SAT, MIP, and tabled planning.
Neng-Fa Zhou, Håkan Kjellerstrand, Jonathan Fruhman
Backmatter
Metadaten
Titel
Constraint Solving and Planning with Picat
verfasst von
Neng-Fa Zhou
Håkan Kjellerstrand
Jonathan Fruhman
Copyright-Jahr
2015
Electronic ISBN
978-3-319-25883-6
Print ISBN
978-3-319-25881-2
DOI
https://doi.org/10.1007/978-3-319-25883-6