[Question] Usage in Games about hypertension HOT 18 CLOSED

from hypertension.

Hello @onehundredfeet,

HyperTensioN already outputs a C++ version, it is just not documented as I am fixing bugs and doing benchmarks before optimizing more and (hopefully) publishing results. A domain.cpp is generated from ruby Hype.rb domain problem [extensions] cpp and can be compiled with GCC with C++11, not tested with other compilers.
Such C++ output was not intended to be embedded in other projects or human readable, and may change over time due to low-level optimizations.

About integrating with games there is a problem, as I never picked an open-source license. The code is just open for other researchers to be able to compare their planners against it. My fear with an open license is that users would expect compatibility or improvements to their unique use-case, fork and start breaking compatibility with the main repo (like Linux distros).
I already had a project that was forked many times with people asking for more features and getting angry when such features were not added their way, sometimes listing such as bugs in their forks. Not a good experience, and that project never had an open license.
Differently from other projects, HyperTensioN is the result of my Masters and PhD research, and I am too attached to it to let such things happen here.

I am not sure if there is a license that would allow usage but not online redistribution, so people would try to maintain compatibility against the main repo, using HyperTensioN as a dependency to be installed locally for its output during development.

I hope you understand,
Mau

from hypertension.

from hypertension.

I think it depends more about which decisions you make during planning than the planner itself.
Some games may require only booleans to represent the intermediate states, while others may require numerical features, and a planner that supports more features will also require more resources to consider more complex elements.
Games also have limited time and resources for their bots, not sure how fast a planner needs to be considering you are already limited, plans are usually short to deal with such.
I am not sure if there are good generic HTN planners for games, they are usually tied to a game engine using their specific programming language, which makes it harder to compare.

from hypertension.

from hypertension.

I am biased towards the algorithm I already use here, Total-order Forward Decomposition, which does not optimize towards shorter plans, it is faster but may repeat some movements if allowed.
If you pick the partial-order algorithm, the planner is free to intertwine branches and obtain shorter plans, but you need to consider more details while describing the domain.
There are also SAT-based ones, but they are not as incremental, as you offload most stuff to a SAT solver with an increasing horizon.

The partial plan part is hard, as the planner may explore a lot of what appears to be part of a plan, only to reach a dead-end, backtrack and start again using other values/branches, just like discovering you should have picked the keys before going towards the car.

HyperTensioN, for example, does not have the partial plan feature you seek.
A single plan is built only after all tasks have been decomposed, for speed and because the partial plan would be misleading in some scenarios, as the example above.
My other planner, HyperTensioN_U, on the other hand, returns at most N plans for the same set of tasks, looking for the most probable/rewarding ones. Keeping track of multiple plans costs more resources, but solves different problems.

And these are the design choices that make it hard to find a one size fits all HTN, which bothers users comparing planners in a single use-case.
I am still thinking/investigating about how I could make the planner core open to others while keeping the system itself closed (at least for now).

Mau

from hypertension.

from hypertension.

You will need to consider this based on your game, some domains have impossible situations, others never have to backtrack.
There is nothing stopping you from adding a branch specifically for an impossible situation and decomposing into a bot going crazy or screaming for help.
TFD handles this, but failure is only returned after everything is explored, and that may cost a lot of time.
Worst case scenario your planner returns failure (no plan) or times-out and you decide what happens.

Mau

from hypertension.

from hypertension.

If you want it for a single heavy game, try to skip it and use a simpler decision mechanism when possible.
Otherwise there is some info in the README and I wrote about it here.

from hypertension.

Hi,

Just saw the discussion and decide to chime in. There is a C++ implementation of a heuristic-search based algorithm called PANDA right here on Github (they also have branches based on SAT). They have a BSD license which is pretty permissive. That algorithm is pretty efficient and has an active community, so that might be a good place to start. There are many other options of HTN planners that competed with HyperTension (our submission) on the last International Planning Competition which you may want to take a look at here, I'm not sure about the license of each and every one of them.

from hypertension.

Thanks @meneguzzi . I'll check them out. I've also found derplanner used in this article . I'm going to see if I can modify it similarly. How does PANDA compare to what's in this small library?

from hypertension.

I have no experience with derplanner, I'm afraid. Thanks for the paper, it really looks like derplanner is focused on games, which might be what you are looking for. Panda is an academic planner, much like HyperTensioN, and, according to the papers I've been reading, its performance is on par with Mau's implementation.

from hypertension.

from hypertension.

Panda has a lot of moving parts, a parser that translates HDDL (and JSHOP's formalism) into something like SAS+ (a representation often used for PDDL planning, i.e. non-hierarchical), and the actual planner / search engine. Out of the box it probably won't be geared to realtime search, but given that it works on the traditional framework of search algorithms with a priority queue as a frontier, nothing prevents you from trying to make it work in realtime. If you change the frontier to a stack, it should have the behaviour of TFD/PFD (a student of mine has done that, so it's not that hard). They also have branches with the kind of loop detection we do in HyperTensioN.

The only problem is, that, as most academic software, it is not brilliantly documented. On the flipside the community around it might answer questions.

from hypertension.

from hypertension.

It depends on the algorithm, if it's A*, it's the distance to the current node in the decomposition plus a heuristic estimate.

from hypertension.

This discussion has diverged from the actual issue and project, you can easily find good tutorials about A* online.
This is the sort of thing I wanted to avoid, as said in the first reply, more features/questions not constructive to the project.

from hypertension.