Skip to content

Instantly share code, notes, and snippets.

@kenwebb
Last active Jul 23, 2021
Embed
What would you like to do?
Getting a cup of coffee
<?xml version="1.0" encoding="UTF-8"?>
<!--Xholon Workbook http://www.primordion.com/Xholon/gwt/ MIT License, Copyright (C) Ken Webb, Thu Jul 22 2021 21:03:28 GMT-0400 (Eastern Daylight Time)-->
<XholonWorkbook>
<Notes><![CDATA[
Xholon
------
Title: Getting a cup of coffee
Description:
Url: http://www.primordion.com/Xholon/gwt/
InternalName: eff45f230c126738760f3498487e5d5b
Keywords:
My Notes
--------
July 21, 2021
TODO
- implement the "getting a cup of coffee" problem in Xholon
- Avatar will start in the Kitchen, will wander around the world looking for required objects
- Avatar will record each location visited and what objects csn be obtained there; will save each location as an XPath expression rather than as a port
- every thing and place is embedded within the world and can only be accessed "physically" rather than as symbols
-
A hierarchically-specified plan is realized as a linear sequence of actions.
For example, ref 1 (p. 526) states:
"The final plan for getting coffee is, thus,
Go to the store,
Buy beans,
Go to the kitchen,
Make coffee,
Pour coffee.
"
In this Xholon workbook, I need to express this as a sequence of Avatar IFLang commands. Something like:
ava.actiion("go store;take beans;go kitchen;build coffee;take coffee;eat coffee")
var ava = xh.avatar()
ava.action("script;\nwhere;\nnext;\nnext;\ntakeclone nextprev;\nnext;\neat coffee;\nwhere")
// result:
where;
You are in kitchen_47.
next;
Moving to coffeeBeanStore_51
next;
Moving to brewedCoffeeStore_53
takeclone nextprev;
next;
Moving to kitchen_47
eat coffee;
Yum.
where
You are in kitchen_47.
References
----------
(1) Cohen and Feigenbaum, The Handbook of Artificial Intelligence, vol.3, Planning and Problem Solving, B. STRIPS and ABSTRIPTS, p.523
() https://en.wikipedia.org/wiki/Stanford_Research_Institute_Problem_Solver
The Stanford Research Institute Problem Solver, known by its acronym STRIPS,
is an automated planner developed by Richard Fikes and Nils Nilsson in 1971 at SRI International.
The same name was later used to refer to the formal language of the inputs to this planner.
This language is the base for most of the languages for expressing automated planning problem instances in use today;
such languages are commonly known as action languages. This article only describes the language, not the planner.
() https://en.wikipedia.org/wiki/Action_description_language
In artificial intelligence, action description language (ADL) is an automated planning and scheduling system in particular for robots.
It is considered an advancement of STRIPS.
Edwin Pednault (a specialist in the field of Data abstraction and modelling who has been an IBM Research Staff Member
in the Data Abstraction Research Group since 1996) proposed this language in 1987.
It is an example of an action language.
() https://en.wikipedia.org/wiki/Action_language
In computer science, an action language is a language for specifying state transition systems,
and is commonly used to create formal models of the effects of actions on the world.
Action languages are commonly used in the artificial intelligence and robotics domains,
where they describe how actions affect the states of systems over time, and may be used for automated planning.
Action languages fall into two classes: action description languages and action query languages.
Examples of the former include STRIPS, PDDL, Language A (a generalization of STRIPS; the propositional part of Pednault's ADL), Language B (an extension of A adding indirect effects, distinguishing static and dynamic laws) and Language C (which adds indirect effects also, and does not assume that every fluent is automatically "inertial").
There are also the Action Query Languages P, Q and R. Several different algorithms exist for converting action languages, and in particular, action language C, to answer set programs.
Since modern answer-set solvers make use of boolean SAT algorithms to very rapidly ascertain satisfiability, this implies that action languages can also enjoy the progress being made in the domain of boolean SAT solving.
() https://en.wikipedia.org/wiki/Planning_Domain_Definition_Language
The Planning Domain Definition Language (PDDL) is an attempt to standardize Artificial Intelligence (AI) planning languages.
It was first developed by Drew McDermott and his colleagues in 1998 (inspired by STRIPS and ADL among others) mainly to make
the 1998/2000 International Planning Competition (IPC) possible, and then evolved with each competition.
The standardization provided by PDDL has the benefit of making research more reusable and easily comparable,
though at the cost of some expressive power, compared to domain-specific systems.
() http://www.cs.toronto.edu/~sheila/384/w11/Assignments/A3/veloso-PDDL_by_Example.pdf
() https://helios.hud.ac.uk/scommv/IPC-14/index.html
IPC 2014
The international planning competition is a (nearly) biennial event organized in the context of the International Conference on Planning and Scheduling (ICAPS).
The competition has different goals, including, providing an empirical comparison of the state of the art of planning systems,
highlighting challenges to the Planning community, proposing new directions for research and new links with other fields of AI,
and providing new data sets to be used by the research community as benchmarks.
() https://helios.hud.ac.uk/scommv/IPC-14/software.html
International Planning Competition 2014
() https://www.icaps-conference.org/
International Conference on Automated Planning and Scheduling
the premier forum for researchers and practitioners in planning and scheduling
() https://www.icaps-conference.org/competitions/
() http://gki.informatik.uni-freiburg.de/competition/
IPC 2020
The 2020 IPC for Hierarchical Planning
ICAPS 2020 has hosted the 2020 IPC for Hierarchical Planning - as proposed in the following paper.
It was the first IPC solely dedicated to Hierarchical Planning and HTN Planning in particular.
Input Language
The competition used domains and problems formulated in HDDL.
Its syntax and semantics are explained in a recent paper.
In addition we have made some minor changes and guarantees for the IPC.
You can find details in the following document.
() https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2020/Hoeller2020HDDL.pdf
HDDL: An Extension to PDDL for Expressing Hierarchical Planning Problems
() https://en.wikipedia.org/wiki/Graphplan
Graphplan is an algorithm for automated planning developed by Avrim Blum and Merrick Furst in 1995.
Graphplan takes as input a planning problem expressed in STRIPS and produces, if one is possible, a sequence of operations for reaching a goal state.
() http://www.philippe-fournier-viger.com/plplan/index.php
KSW a Java implementation of the Graphplan algorithm; I downloaded the .jar file which has Java source code; includes 2 examples
PL-PLAN : A Java Open-Source AI Planner
Introduction
PL-PLAN is an open-source ai planner written during the summer of 2004 by Philippe Fournier-Viger and Ludovic Lebel as a side project.
The goal was to create a simple AI planner to experiment many search techniques for classical states-space exploration,
including the Graphplan algorithm, and six algorithms based on partial-order theory.
PL-PLAN can be used as a library from any Java programs.
A software with a graphical user interface (cf. figure 1) has been developed to run multiple random tests to compare the various algorithms of PL-PLAN.
Tests results can be exported to comma-separated files that can be read by Microsoft Excel.
This software is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 2.0 Canada License.
() http://emplan.sourceforge.net/
other implementations of Graphplan
C++, Java
() https://sourceforge.net/projects/jplan/
another Java implementation; 2004
() https://en.wikipedia.org/wiki/Category:Automated_planning_and_scheduling
Category:Automated planning and scheduling
The main article for this category is Automated planning and scheduling.
() https://en.wikipedia.org/wiki/Automated_planning_and_scheduling
Automated planning and scheduling, sometimes denoted as simply AI planning,
is a branch of artificial intelligence that concerns the realization of strategies or action sequences,
typically for execution by intelligent agents, autonomous robots and unmanned vehicles.
Unlike classical control and classification problems, the solutions are complex and must be discovered and optimized in multidimensional space.
Planning is also related to decision theory.
() https://en.wikipedia.org/wiki/Hierarchical_task_network
In artificial intelligence, hierarchical task network (HTN) planning is an approach to automated planning
in which the dependency among actions can be given in the form of hierarchically structured networks.
() https://en.wikipedia.org/wiki/Behavior_tree_(artificial_intelligence,_robotics_and_control)
A behavior tree is a mathematical model of plan execution used in computer science, robotics, control systems and video games.
They describe switchings between a finite set of tasks in a modular fashion.
Their strength comes from their ability to create very complex tasks composed of simple tasks, without worrying how the simple tasks are implemented.
Behavior trees present some similarities to hierarchical state machines with the key difference that the main building block of a behavior is a task rather than a state.
Its ease of human understanding make behavior trees less error prone and very popular in the game developer community.
Behavior trees have been shown to generalize several other control architectures.[1][2] Mathematically, they are directed acyclic graphs.
Behavior trees originate from the computer game industry as a powerful tool to model the behavior of non-player characters (NPCs).
They have been extensively used in high-profile video games such as Halo, Bioshock, and Spore.
Recent works propose behavior trees as a multi-mission control framework for UAV, complex robots, robotic manipulation, and multi-robot systems.
Behavior trees have now reached the maturity to be treated in Game AI textbooks,[13][14] as well as generic game environments such as Unity (game engine) and Unreal Engine (see links below).
Behavior trees became popular for their development paradigm: being able to create a complex behavior by only programming the NPC's actions
and then designing a tree structure (usually through drag and drop) whose leaf nodes are actions and whose inner nodes determine the NPC's decision making.
Behavior trees are visually intuitive and easy to design, test, and debug, and provide more modularity, scalability, and reusability than other behavior creation methods.
Over the years, the diverse implementations of behavior trees kept improving both in efficiency and capabilities to satisfy the demands of the industry,
until they evolved into event-driven behavior trees.
Event-driven behavior trees solved some scalability issues of classical behavior trees by changing how the tree internally handles its execution,
and by introducing a new type of node that can react to events and abort running node
Nowadays, the concept of event-driven behavior tree is a standard and used in most of the implementations, even though they are still called "behavior trees" for simplicity.
) https://www.primordion.com/Xholon/gwt/wb/editwb.html?app=24fbc868269ea55b784fde196b209e18&src=gist
Behavior Trees
KSW I have experimented with Behavior Trees in Xholon
() https://en.wikipedia.org/wiki/Process_ontology
In philosophy, a process ontology refers to a universal model of the structure of the world as an ordered wholeness.
Such ontologies are fundamental ontologies, in contrast to the so-called applied ontologies.
Fundamental ontologies do not claim to be accessible to any empirical proof in itself, but to be a structural design pattern,
out of which empirical phenomena can be explained and put together consistently.
Throughout Western history, the dominating fundamental ontology is the so-called substance theory.
However, fundamental process ontologies are becoming more important in recent times,
because the progress in the discovery of the foundations of physics spurred the development of a basic concept able to integrate
such boundary notions as "energy," "object", and those of the physical dimensions of space and time.
() https://en.wikipedia.org/wiki/Reactive_planning
In artificial intelligence, reactive planning denotes a group of techniques for action selection by autonomous agents.
These techniques differ from classical planning in two aspects.
First, they operate in a timely fashion and hence can cope with highly dynamic and unpredictable environments.
Second, they compute just one next action in every instant, based on the current context.
Reactive planners often (but not always) exploit reactive plans, which are stored structures describing the agent's priorities and behaviour.
]]></Notes>
<_-.XholonClass>
<PhysicalSystem/>
<CoffeeWorld/>
<Location>
<Kitchen/>
<Store>
<CoffeeBeanStore/>
<BrewedCoffeeStore/>
</Store>
<Bank/>
</Location>
<Thing>
<Coffee/>
<Beans/> <!--<CoffeeBeans/>-->
<Grinder/>
<Water/>
<Money/>
</Thing>
</_-.XholonClass>
<xholonClassDetails>
<Avatar><Color>red</Color></Avatar>
</xholonClassDetails>
<PhysicalSystem>
<CoffeeWorld>
<Kitchen>
<!-- Avatar -->
<script>
// commands for built-in Avatar
var akm = '{ \
"SHIFT":"true", \
"NOSCROLL":"true", \
"UP":"exit", \
"DOWN":"first", \
"LEFT":"prev", \
"RIGHT":"next", \
"d":"drop first", \
"e":"eat coffee", \
"f":"flip", \
"i":"inventory", \
"l":"look", \
"n":"enter nextprev", \
"p":"pause", \
"s":"step", \
" ":"step", \
"t":"takeclone nextprev", \
"w":"who;where", \
"z":"param transcript toggle;", \
"?":"help keymap", \
"/":"help commands", \
"0":"go link0", \
"1":"go link1" \
}';
$wnd.xh.avatarKeyMap(akm);
const ava = $wnd.xh.avatar()
ava.action("who;enter;enter;enter;where;appear")
//# sourceURL=Kitchenbehavior.js
</script>
<Grinder/>
<Water state="cold"/>
</Kitchen>
<CoffeeBeanStore>
<Beans multiplicity="1"/> <!-- TODO maxClones="5" ??? -->
</CoffeeBeanStore>
<BrewedCoffeeStore>
<Coffee state="brewed" multiplicity="1"/>
<script>
var coff = this.parent().first();
this.remove()
while (coff) {
coff.state = "brewed"
coff = coff.next()
}
</script>
</BrewedCoffeeStore>
</CoffeeWorld>
<!--<Animate efParams="&quot;mode&quot;:&quot;tween&quot;"/>-->
<Animate
selection="#xhcanvas"
xpath="./PhysicalSystem/CoffeeWorld"
duration="1.0"
cssStyle="stroke-width: {0px;}"
efParams="{
&quot;selection&quot;:&quot;#xhcanvas&quot;,
&quot;sort&quot;:&quot;disable&quot;,
&quot;width&quot;:500,&quot;height&quot;:500,
&quot;mode&quot;:&quot;tween&quot;,
&quot;labelContainers&quot;:true,
&quot;includeId&quot;:true,
&quot;shape&quot;:&quot;circle&quot;,
&quot;useIcons&quot;:true,
&quot;maxChars&quot;:-9,
&quot;togglePortColors&quot;:false,
&quot;supportTouch&quot;:false,
&quot;supportClick&quot;:true,
&quot;supportContextmenu&quot;:true,
&quot;supportDblclick&quot;:false,
&quot;fontSizeMultiplier&quot;:2.6
}"
/>
</PhysicalSystem>
<SvgClient><Attribute_String roleName="svgUri"><![CDATA[data:image/svg+xml,
<svg width="100" height="50" xmlns="http://www.w3.org/2000/svg">
<g>
<title>CoffeeWorld</title>
<rect id="PhysicalSystem/CoffeeWorld" fill="#98FB98" height="50" width="50" x="25" y="0"/>
<g>
<title>Kitchen</title>
<rect id="PhysicalSystem/CoffeeWorld/Kitchen" fill="#6AB06A" height="50" width="10" x="80" y="0"/>
</g>
</g>
</svg>
]]></Attribute_String><Attribute_String roleName="setup">${MODELNAME_DEFAULT},${SVGURI_DEFAULT}</Attribute_String></SvgClient>
</XholonWorkbook>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment