Distribution of AttributeInstances on Hardware

Important Factors for Distribution:

* amount of communication needed with other AttributeInstances
* close neighbours with which frequently interact
* workload - number of requests

Conditions in a Plan as a Tree Structure

goal -> action + condition*
condition -> action + condition*

In Crackpot, we store each attribute and all conditions on an attribute. This means it is possible to infer: a particular condition c is satisfied by which actions, and these actions have in turn what conditions.

Visualizing conditions as a Tree structure is helpful:

1) Condition: If a condition c is no longer needed due to change in situation, the whole "subtree" of c (containing actions and conditions) should be removed, unless a certain action participates in achievement of another goal.

The queries from the Tree structure in the above scenario are:
a. get all action instances needed to satisfy a condition instance
b. get condition instances of an action instance
c. get all condition instances satisfied by an action instance

2) Cases (for the case base) - which heuristic helped achieve which condition in what scenario. In scenario, we can probably store: the condition that was satisfied and the existing states of the attributed participating in the condition. In the case, we also need to store what change was produced by the heuristic.

If the case base stores the whole tree of a condition, the tree can be copied and applied in another situation.

3) Infer goodness of a heuristic - How to update the goodness of a heuristic? If a heuristic participated in satisfying a condition of an action that was executed and yielded reward R, the heuristic should be awarded its share of R. How to determine the share?

As I earlier mentioned, the Cost value of a condition should store not just the difficulty of achieving the cost, but also the priority of the goal. A heuristic is best if it reduces the difficulty of a high priority goal using quite minimal resources and time. Once a heuristic is classified as better, the difficulty of the goal reduces. So within a closed-loop, the difficulty measures should be updated as well.

4) Plan Merging - In plan merging we are interested in reducing the size of merge(A, B) from size(A) and size(B). Plan merging is useful in parallelization of planning as well as in case-based planning. If A and B share a condition c such that the plans can be moved and adjusted to need to achieve c only once, all actions needed to achieve c need not be duplicated.

Using SQLite Database for Crackpot

Case for Database
There are several places where database can be useful in Crackpot. Storing and retrieving plans. Storing data from GUI for replay. Storing information for long term, learning etc. In summary, any place which is not in the critical performance path.

SQLite
The use of a database can simplify the work needed for storing and retrieving information. Some candidate databases are: BerkeleyDB, SQLite, MySQL, PostgresQL. Out of these, SQLite is a high performance and simple database with an open license. SQLite seems fit for our purposes.

In-memory databases
There are some databases which can be used to store and query information within the main memory (RAM). SQLite also supports in-memory databasing.

SQLite with C++
A good C++ wrapper for SQL in general is seems to be SOCI. Unfortunately using it for SQLite might need some work. But still seems to be a productive choice.

Crackpot FAQs

Planning System

• Why do we need a class ObjectType and another called ObjectInstance? Why not just one class Object (refering to ObjectInstance)?

The information about the ObjectType is available only at runtime. If we have just one class Object, we won't be able to "tag" apple objects as of "apple" type. We want to store types of objects. You can think of ObjectTypes as tags to ObjectInstances.

• What is ground and formal ObjectInstance?
  

In the ActionType "OpenDoor(d: DoorType, p: personType)", d is be an "Object Variable" or a placeholder for an ObjectInstance. In ActionInstance, it becomes "OpenDoor(door0, person0)". Here door0 and person0 are actual objects in the world. The "Object Variables" are currently called Formal ObjectInstances and "actual objects in the world" are called Ground Object Instances.

C++/Programming General

• I have a particular technical question. Where can I get help?
  

Besides the usual means, you can also search or ask on online forums. Before asking there, make sure you have done a good research on it on google (and include your research done along with the question). In particular I like stackoverflow.com

C++ - Beginner Level

• Good resources?
  

See the article "A Quick Introduction to C++"

• How do I handle cyclic dependencies in C++? For example, class A uses class B, and class B uses class A?

See http://www.eventhelix.com/realtimemantra/HeaderFileIncludePatterns.htm

How it is and How it Should be

Changes and refactoring are an intrinsive part of evolution of any software. There is a lot of changes needed in Crackpot (code in trunk). Some of the changes are small - like renaming certain classes/functions and others are large - like architecture changes. Also see another list of needed changes in (crackpot_directory)/TODO.txt.

I am labelling the changes with severity labels of low, medium and high.

Objects and Attributes

Severity: Medium

Each ObjectType can have a "self" attribute which refers to the object itself. This will allow the existing framework of attributes to extend to include object references. For example, to refer to ObjectInstance a1, we can say "a1.self". (In the current implementation, a1 will be a ValueInstance. This is more of a hack.).

Severity: Medium

Formal ObjectInstance should be renamed as ObjectInstancePlaceHolder.

Actions

Severity: Medium

Right now contributions and conditions are connected with ActionType, while actually they should be connected to ActionTaskType.

Domain definition

Severity: Low

Right now all the information about the domain are read into a class called DomainPackage, which maintains repositories or objecttypes, objectinstances, attributetypes, actiontypes and so on. This has made DomainPackage class too large to the extent that it is exploding now.

In the future, we should have separate classes ObjectTypeRepository, ActionTypeRepository, and ObjectInstanceRepository. These repositories should handle name-based queries also like getObjectInstanceWithNameOfType(). ObjectTypes can contain its list of AttributeTypes and ActionResourceTypes. (Optional) Small factories like ObjectTypeFactory can be introduced; this has the logic to build ObjectTypes. ObjectInstanceRepository can contain the map from ObjectType to its ObjectInstances.

Finally, all the queries regarding the domain (and asked by heuristics) will be handled by PlanStructure class. So it can be something like:

class DomainQueryHandler
{
// all get and set functions related to domain
// implements facade that hides the various domain related repositories
};

class PlanStructure: public DomainQueryHandler {
// ...
};

Directory Structure
Update: Our colleague, Sima, completed the refactoring into the new directory structure.

Severity: Medium

As per Planning Group meetings, the directory structure has to evolve into something like this (this structure is not finalized, but will be soon):

PlanManager
PlanStructure
|- Object
|- Action
CostManager
CostStructure
CostCenter
|- Heuristics

Types and Instances

We can form a convention that functions to create instance will be a member function of type. For example, a ConditionType has a member to create ConditionInstance.

Complex Actions

Severity: Medium

Sometimes the further course of plan depends on result of performing an action. For example, try to open the door. If door is locked, it won't open. Then the agent must look for the key. This can be encoded as a monitoring ActionTask in the OpenDoor action: [If (monitor(door) == door-locked) insert look-for-key action into plan]. We need to develop/reuse a logic for this purpose. Further there may be monitoring loops within actions, like [while (monitor(water-boiling) == false) {}].

Using Description Logic

Severity: Medium

Our rich-world description should be based on a formalized logic. This helps in interfacing with other tools, communication with other groups and reusability in other situations. Description Logic is one such logic. Description Logic is the basis for several semantic web constructs. We can use Description Logic constructs for objects, actions, plans and goals.

Implementation of More Examples

Severity: Medium

Both domain independent and domain dependent techniques can be used, for example for Settlers domain: http://planning.cis.strath.ac.uk/competition/ .

Implementation: Build Related

We need to normalize the build process across compile time options, include directories, etc. See http://stackoverflow.com/questions/222827/how-do-you-organize-your-version-control-repository/304036#304036 for a good build strategy.

Use of Templates

We should move to using templates in a greater manner - namely for all types that do not need run-time polymorphism. The benefits of using templates are:
- policy-based class design helps to prepare more reusable components
- being purely syntactic entities they are also minimally intrusive to other class

I'm sure there is more to come. I expect this entry to be updated frequently.

Cost Repair Guidance

In this entry we list some good heuristics for Cost Repair. These can be used by CostManager to select appropriate Costs to fix.

Do Something Now

Since limited time is available before execution starts, actions that need to be taken early on should be decided first, locked and sent for execution. Suppose there are two actions that could be executed under the current environment, a1 and a2. But executing one of the two actions is important right now to be able to succeed within time.

This is a question related to deliberation versus reaction. Should an agent think more or start execution? How much should the agent think, and how much execute?

To fix an action early on, there may be a way to measure the difficulty of reaching the goals from the states s1 and s2, reached when a1 and a2 respectively are executed in plan. Once the CostCenter has computed, for example, that s1 is much farther from goal than s2, a2 may be locked for execution.

Difficulty versus Priority: Note that difficulty of reaching a goal is a separate concern from the priority or urgency of reaching the goal. Each Cost should contain information both about difficulty and priority.

Estimating difficulty of reaching goal: How to estimate the difficulty of reaching the goal? Estimation should not consume so much time that it offsets the benefit of finer approximation of estimate. Depending on the situation, finer estimation may be more useful or not. One question in this regard is whether the estimate should be an admissible (link) estimate or not? If there are dead-ends in the topology of the search space, it is better to estimate their possibility of existence on our selected path.

Soundness: The plan formed before the execution should make sense. In a robot-doors domain, it does not make sense to "open the door" if the precondition that the robot is close to the door is not satisfied (the robot actually is 10m away from the door - in this case, the robot actuators might try to "open the door" in thin air). It is important that the plan sent for execution is sound, and does not cause a catastrophic effect (such as malfunctioning of robot actuators).

Most Constraining Choice First

Another heuristic for cost repair guidance is that the most constraining action should be fixed first. If there is some action that must be carried out (and there is no other choice), then it should be locked. This is similar to the fail-first principle used in CSP (see the tutorial on CSP by Bartak in ICAPS 2008). A good paper that significantly advances the idea of constraining choices is [2].

Most Likely Choice First

The instantiation value of a choice should be so that it makes the likelihood of production of plan the easiest/fastest. This is similar to the succeed-first principle used in CSP.

Case Based Reasoning

From the previous applications of heuristics, idea about 1) goodness of application of each heuristic, 2) time the heuristic took, 3) resources that were used by the heuristic, 4) how uncertain we are of the goodness of the heuristic, in the respective state may be stored. Next time the better heuristics for the purpose may be used.

Criteria for Scheduling Repairs

Some criteria for decision making for scheduling repairs are: 1) Available time to complete planning for the goal, 2) available resources, 3) Difficulty of the goal and 4) Priority of the goal.

Avoiding Interference Between Goals

If there are two goals that need mutual exclusive conditions to achieve the two goals, the two goals cannot be simultaneously achieved. This means one of the goals must be abandoned if there is not sufficient time available to achieve both of them [3].

I am sure there are more meta/hyper-heuristics for search guidance. I will write later on those.

References

[1] "Planning by Rewriting - Efficiently Generating High-Quality Plans" Ambite and Knoblock. They identified some transformation rules - collapse, expand, reorder, parallelize - to alter the plan within one iteration. May be somewhat useful reference for metaplanning.
[2] "Finding Crucial Subproblems to Focus Global Search" Susan L. Epstein, Richard J. Wallace. ICTAI 2006.
[3] "Detecting and Avoiding Interference Between Goals in Intelligent Agents"

Heuristics Selection - Context Matching or Probabilistic Selection? Careful or Faster?

We target the problem of selecting proper heuristics for repair of a particular cost. The following things are important here: 1) What features of the current situation are important in selection of heuristic (and need to be stored)?, 2) How to measure the goodness of various heuristics in this situation?, 3) Given the features and goodness of various heuristics, how to select a good heuristic for application?

Availability of limited memory implies only limited number of features of a situation can be stored. Availability of limited computational resources implies only a little computation can be used to match the current situation with the features stored and to evaluate the goodness of various heuristics for updation of heuristic preferences. Also only limited time can be used for selecting good heuristic for application.

Features
A heuristic internally has several choice points. For example, a heuristic to add an action has internally the choices: which action to insert, which parameters to use to instantiate the action, which start time of action to use. Each choice point needs to store:
1) The context of the choice (for example, the current state and the desired state)
2) Evaluated goodness in the context. It may be noted that there may be defined a distance function between contexts.

Goodness
The goodness of a heuristic may be measured using a machine learning technique like Q-Learning.

Selection
The two extremes of implementation of heuristics selection are:
1) We store nothing, only a few simple choices for selection of appropriate class of heuristics. This is close to the current implementation. We choose an appropriate heuristic more or less randomly (actually it is not completely randomly but guided by the past experiences of heuristic selection (link to Alex's paper on this)). In this case, we expect fast reaction (due to simple heuristic selection), but will perform well only in domains where mistakes are tolerable and/or correctable. This is a less careful approach, but faster.
2) We store many features of each situation. Then the investigation of which heuristic to apply in a particular case takes more time. This is a more careful approach, but slower.
It may be argued that the faster approach may not be preferable for huge (exponential) search spaces with non-trivial structure. Randomly and quickly assigning some values for search may not work well when there is a huge space to search.

Indeed one way to approach the problem is to try something trivial. If it works then good, else try more time-taking more careful techniques. The preference values of what do not work may be temporarily reduced.

Should Heuristics refer to PlanManager?

We decided earlier that each Cost is fixed by one particular CostCenter - this mapping is statically defined. While this decision simplifies the workflow of Cost Repair, it creates new problems.

Take the case of Logistics domain. We have actions of LoadTruck, UnloadTruck and MoveTruck that modify the location of a packet. We have a goal to move a certain packet_1 from one location to another. According to our decision, this goal is a Cost to be repaired by the location attribute of packet_1.

The location attribute of packet_1 knows about the actions that alter its value. The actions LoadTruck and UnloadTruck do. However, for repair of the Cost, a truck is needed (on which the packet will be loaded). Now the location attribute of packet_1 does not know anything about a good truck to instantiate LoadTruck.

There are two options here: 1) the location attribute instantiates LoadTruck with a random truck (in the hope that the resultant cost will be fixed later), or 2) the location attribute asks the PlanManager about a good truck.

In the first option, we need to introduce a heuristic changeParameter to change a parameter of the LoadTruck action later. Also, probably it is better for the PlanManager to remember (and not lose the information) that a random truck was used to instantiate the LoadTruck action and fix the associated cost in this manner. One simple way to implement this is by using a dummy truck (which is a placeholder for a real truck) to instantiate LoadTruck. Cost due to dummy truck will be fixed by a new changeParameter heuristic.

The second option is quite intrusive change, more unpredictable and thus more difficult to parallelize. It is more unpredictable because the PlanManager may be busy with other tasks when the request for a good truck came, in which case the requesting location attribute would have to wait. However, it is noted that the second option may be needed to be used in more complex repairs, but not in the simple case we are dealing with right now.

Another thing: Note that in the first option, we would like to call changeParameter heuristic (and no other heuristic) whenever the Cost is on the dummy object. Therefore, in general a CostCenter must perform some pre-inspection to select an appropriate class of heuristics to fix a particular cost (this pre-inspection right now includes looking at the type of cost - whether it is a goal cost of condition cost).