2009-07-29

Behaviour Tree Design

Permalink 17:03:59, Categories: GSOC 2009  

Overview
The core components of a basic behaviour tree implementation are selectors, sequences, conditions and actions. With just these tools it is possible to recreate most finite state machines (FSMs) in a more intuitive manner. By then adding decorators the behaviour tree becomes a more powerful tool whilst maintaining its intuitiveness.

As conditions and actions can be created by making use of the refactored CEL triggers and rewards respectively the implementation of these core behaviour tree components will serve as a proof of concept of the usefulness of the recently completed Quest refactor.

More complex features of behaviour trees include memory management techniques and a scheduler controlled implementation. Both of these techniques could potentially be very useful within CEL but are beyond the scope of the proposed deliverables and would be unachievable in the remaining time frame of GSoC 2009. However, it is my intention to design the interface in a manner that will ease any future work on these features.

The remainder of this document outlines the tools I intend to develop and document in the coming weeks. Whilst I have provided a brief description here of their functionality, anybody interested in this tool is highly recommended to visit AiGameDev, specifically these freely available resources: A Brief Written Overview and A More Detailed Video Series. I was fortunate enough to sign on to the premium membership of this site with the initial payment from the GSoC project and I would have to say it has been crucial in the design of this tool.

Interface (iBTNode)
A behaviour tree is to be executed each time an entity needs to decide upon an action. The tree evaluates from the root evaluating each chosen child node. Each node returns a boolean to indicate the success or failure of that node. Therefore, the interface requires an execute method that returns a boolean. As it is intended that the behaviour tree may make use of the refactored celParameters class, this method must receive an argument of this type.

To connect nodes and leaves of type iBTNode, each node must maintain an array of children and provide methods for adding to this array.

To use a behaviour tree, the user must first create each node/leaf and connect them. Once constructed, an entity needing to choose an action will execute the root node which in turn, upon deciding the correct child, will execute the chosen child node and pass on the parameters. Eventually the root node will receive a boolean value indicating the success or failure of its child and, presuming its own execution is complete, will return its own success or failure to the user. The interpretation of this final return status will be implementation specific in so much that a return of false is not necessarily a negative result dependent on the design of the tree itself.

To summarise, the intended iBTNode interface is:
virtual bool execute (const celParams& params)
virtual bool addChild (iBTNode* child)

Selectors and Sequences (plgSelectors)
Selectors and Sequences, or collectively known as composites, are nodes in a tree with multiple children that control which children to execute. Selectors work through the children nodes until one child returns success, if a child returns success the selector stops executing children and itself returns success. However if no children succeed the selector also fails. They are often referred to as OR nodes, as one child or another is executed.

The logical opposite to selectors is sequences. Sequences execute children in order until one fails. If all children succeed the sequence succeeds but if any child fails the sequence immediately fails and stops to execute any further children. They are often referred to as AND nodes, as the first child and the second child and so on are executed.

Due to the name clash in CEL and CS with both the refactored CelSequences and the existing CSSequences, my current design decision is to instead name the sequences composite a SequentialSelector.

In addition, the selector composite by default selects children from left to right (dictated in code by the order they are added to the node) however this selection of one specific child can be implemented in numerous methods increasing the number of behaviours achievable. To demonstrate this capability I intend to implement both a standard selector and a random selector.

To summarise the following selectors are intended to be implemented during GSoC:
- DefaultSelector
- SequentialSelector
- RandomSelector

Decorators (plgDecorators)
Decorators, like selectors before, are nodes in the behaviour tree with the difference being that decorators tend to have one child. Their purpose is not to select a child to execute but to themselves perform some computation before passing execution to the child.

I intend to implement decorators for loops, limiting the number of times a child can execute, and negating the return value of a child (so that a sequence can continue UNLESS a condition has fired.) For a more complete list of example decorators please see http://aigamedev.com/hierarchical-logic/decorator/. If any are of particular interest to readers please let me know and I will try my best to implement them within the time frame.

To summarise the following decorators are intended to be implemented during GSoC:
- LoopDecorator
- ExecutionLimitDecorator
- NegateReturnDecorator

Conditions and Actions (plgBehaviourTree)
Finally, the leaves of a behaviour tree are made up of conditions and actions. In CEL we already have the concepts of triggers and rewards and as such the implementation of these leaf nodes is partially complete.

In essence actions are essentially rewards except actions must return a success or failure and rewards currently do not. I intend to modify slightly the interface to rewards to return this value and update the refactored rewards to implement this change. This should have no effect upon the quest implementation. All nodes of a behaviour tree will have to implement the interface iBTNode, I do not however intend to add this to the refactored rewards. Instead I will implement a wrapper BTAction the implements the iBTNode interface and executes an action.

Similarly triggers do not directly fit into the behaviour tree paradigm. Instead of waiting for a trigger to fire and choosing an actions based on this, behaviour trees check if a trigger has fired at the time of their evaluation and base their choice on if it has already occurred. Therefore another wrapper class is needed, TriggerFiredCondition. This condition will return false if checked before the trigger has fired and true after.

Conditions are not however limited to triggers firing. Instead conditions may include, for example, checking the health of an entity that the behaviour tree belongs to. A generic condition that can be implemented is checking the value of a parameter. The condition, ParameterCheckCondition, will be set up with the name of the parameter, the value and whether to check for equal to, less than or more than.

Other conditions will be application specific and cannot at this time be implemented. However, users of the behaviour tree can easily create their own conditions by implementing the iBTNode interface within their class and returning a boolean based upon the condition they desire to check.

To summarise the following leaf nodes are intended to be implemented during GSoC:
- BTAction
- TriggerFiredCondition
- ParameterCheckCondition

Please note: This document is a work in progress and will be updated with the projects progress including any updates brought to attention in the mail group discussion.

2009-07-22

Quest Refactor Ending... Behaviour Tree Beginning

Permalink 20:19:31, Categories: GSOC 2009  

Hello CrystalSpace,
This weeks work has largely involved testing, cleaning and documenting the code of the refactor. I am glad to say that the vast majority of triggers and rewards are fully factored out and functional within the testing application. My aim is to have the tutorial cover all current triggers and rewards so that there is an exhaustive reference on the purpose and use of each of these tools. Some of you will have noticed my request for examples for a select few of the rewards and triggers I do not currently have covered. I would be very grateful for anyone with experience of these tools to add to the mailing list conversation however they can. For convenience the conversation can be viewed at:
[Cel-main] Example Uses of Specific Rewards/Triggers‏

Outside of adding these remaining rewards and triggers to the tutorial program, I also need to bug fix the sequence refactor which is currently non-functional and implement cel expressions into triggers and sequences. I remain confident that these goals are all achievable within the time frame of the GSoC project.

However, as stated last week, I intend to start the Behaviour Tree implementation tomorrow. More specifically, I have shortlisted a number of papers and tutorials that I wish to review before proceeding. Over the next couple of days I will split my days between closing the final remaining quest refactor tasks and reading around the topic of behaviour trees. I will then move on to thoroughly designing the behaviour tree implementation and intend to have a first draft interface committed to svn by the time of my post next week. Again I will split my workload throughout this remainder of the next week between the behaviour tree and quest refactor projects. My priority at this time is the behaviour tree implementation as I am determined to reach this significant deliverable before the final google deadline, but I will remain vigilant of my progress on the quest refactor to ensure the remaining refactor tasks are also complete before the final deadline. If need be I will return full time to the quest refactor later into the summer.

As always questions, queries and comments by IRC, email or this blog are greatly appreciated.
Kind Regards, Sam

2009-07-14

Midterm Schedule Review

Permalink 18:15:23, Categories: GSOC 2009  

Hello CrystalSpace,
As some of you will know this past week has seen the completion of the mid-term reviews. I am very proud to have passed this milestone and look forward to completing the project in similar success. Thank you to Guillaume for all his continued support and to the community as a whole for all your help.

Given this mid-point in the programme it seems a sensible time to review the schedule and update it in relation to the progress made. I will shortly after making this post bump the schedule to the top of blog for clarity's sake.

This weeks progress was initially focussed on the factor out of sequences, and secondly on the testing of the refactor as a whole. The testing has highlighted that the sequences are currently non-functional and will require some further work. As previously stated the testing application (appquesttest) is intended to be the basis of the refactored-quest tutorial, and so this time spent testing has also seen further development of the tutorial program.

My intention is to continue working on the refactor up to a strict deadline of next Wednesday's post (22nd July). My reasoning for this is that if work does not begin promptly upon the behaviour tree implementation, I may get stuck throughout the program in developing features for the quest system and fail to produce one of my key deliverables; the BT.

Given this deadline, I am afraid the previous intended delivery of nesting FSM's is unlikely to be accomplished at this stage. However, I have as suggested by google left the majority of the final week for finalising the project. Provided I meet the set deadline of August 12th for the BT work, I will still have a solid working week to work on additional features for the refactored quest.

Therefore, the new schedule splits the refactored quest schedule into achievements in the section "Progress", goals intended for completion before 22nd July in the section "To Do" and tasks to attempt once the BT is completed in the section "Time Permitting." The tasks that will be attempted time permitting, are ordered in the intended series of attempting them. Given it was an originally proposed deliverable I have put the allowance for nesting quests at the top of this list. However, if higher priority in any of these additional tasks is desired please feel free to contact me.

Some may notice that I have removed the suggested potential to factor out sequences entirely, given the amount of work I have put in to factoring them out of quests I believe this would be detrimental to the amount achieved by this project. Therefore, whilst I am not disagreeing with this as a potential development decision I do not intend to complete this during the summer of code program.

I have also moved the additional suggestion to implement cel expressions in sequences up from an additional request into an intended deliverable. From my early look into how to add this feature to triggers, I believe that it should be achievable to add expressions to both triggers and sequences within the new quest refactor deadline. I hope that this can at least partly make up for the delay and possible lack of implementation of the nesting deliverable.

Finally, reader's may have noticed this blog was published a day early this week. My graduation is occurring this Thursday and given the long journey and early start we are travelling up tomorrow. This will limit my productivity for the next couple of days, but I will do my best to stay in contact via email if anyone has any queries or suggestions with regard to this new schedule.

Thank you all again for your support, Sam

2009-07-08

All Rewards & Triggers Refactored

Permalink 16:19:37, Categories: GSOC 2009  

Hello CrystalSpace,
With the deadline for the Quest refactor looming I am happy to announce that I am about to commit the final 8 refactored triggers. This will complete the refactor of all rewards and triggers. Leaving just the sequences to be worked on in the remaining days. My intention now is to spend tomorrow working on sequences, Friday on testing the refactor and Saturday cleaning up the code.

Therefore, a working refactor should be commited on Friday. However, this will also still consist of all code for the previous implementation as currently the refactored rewards are running alongside the old rewards to allow for their behaviour to be tested against the original behaviour. Once those tests are completed, I will clean the code by removing all of the previous implementation. My plan is to have this done on Saturday.

This week I have also fixed the parameter based bug that was agitating me during last weeks post. Thank you to Res for his continued efforts to support me on this problem. Finally, this morning I merged again with trunk, as recommended by Guillaume, I intend to do this weekly alongside these posts in the hope of easing the integration of my work with the project at the end of the summer.

As always any questions, please feel free to contact me.
Kind Regards, Sam

2009-07-01

Light Week -> Heavy Week

Permalink 22:42:48, Categories: GSOC 2009  

Hello CrystalSpace,
Progress this week has been relatively slow. Whilst factoring out the change property reward, I discovered a dependency on Quests that I did not fully understand. I must highlight my thanks here to Jorrit for taking the time last Friday to talk me through parameters and helping me to appreciate their use. This has caused a slight rewrite of some of the existing code that has raised a new bug, that I have been cursing for the past few hours. My patience has worn thin, I will reapproach the problem fresh tomorrow and contact the list if or when the problem continues.

The result of this work has added another plugin to the Quest refactor, implementing parameters outside of quests so that they can be used in rewards, triggers and sequences without any dependency on Quests. The results so far will be committed to svn shortly. Under vknecht's advice I will begin to commit to svn more regularly now.

Finally, as mentioned in opening this has been a relatively slow week. I moved out of my old uni house this weekend and back home for the summer. I fully intend, however, to now make up for this light week by putting in a big effort this week to push to meet the Quest refactor deadlines.

Kind Regards, Sam

-------------------------------------------------------
UPDATE: 06/07/09
This bug is no longer troubling me.
Relieved, Sam :)

2009-06-24

Early Refactor Success

Permalink 20:36:40, Categories: GSOC 2009  

Hello CrystalSpace,
This weeks work has been focussed on completing the factoring out of my first reward (debugprint.) This work took significantly longer than initially expected, but I believe that I have learnt a lot from the experience and am confident that the process of factoring out the remaining rewards will be trivial.

I am now putting together a test program that makes use of all rewards, so that I can test the new implementation of each. This program will later serve as the basis of the quest tutorial. From my work with the system I believe there is a firm need for a singular collated example of all rewards and triggers to increase the community's usage of this feature and look forward to providing this.

Finally, I will be posting shortly after this post a formalised list of deliverables. My current progress is behind the initial deadlines set out in my project proposal. At the time I underestimated that time I needed to become familiar with the CS/CEL architecture. However, I believe that I have also overestimated the time needed to implement a behaviour tree. Therefore, I am still confident that all of the promised deliverables will be accomplished in the timeframe of the GSoC program. In addition, a number of other requests have been made for modifications to quest that I hope to cover once the promised refactor and BT implementation is completed. My intention for this post is to update it periodically to show my progress.

That is all for this week, as always please feel free to contact me if you have any suggestions, queries or complaints.

Kind Regards, Sam

2009-06-17

Coding Has Begun

Permalink 14:16:19, Categories: GSOC 2009  

Hello CrystalSpace,
My minor projects late last week and this weekend have come to an end succesfully. I now feel comfortable working with the SCF, Quests and smart pointers. Thank you to everyone on the mailing lists and irc channel that have helped me overcome this initial hurdle.

I have now begun coding the deliverables promised and have made a start on factoring the reward debug message out of quests. My cel workspace now contains a new project plgrewards that compiles a dll containing plugins for each of the rewards and I intend to create something similar for the triggers shortly. I have a busy weekend ahead of me but believe that significant progress will be made on the refactor over the next week / week and a half.

I also intend to publish a formalised list of deliverables with estimated deadlines. I believe there is some way to publish to the blog so that this list will remain as the top post, if so I will periodically update that post to announce deliverables submitted and to show my progress.

As always please feel free to question, poke or criticise me either openly here, in irc, the mailing list or privately by email. I appreciate any and all input on this project.

Kind Regards, Sam

2009-06-10

Exams Over

Permalink 12:02:23, Categories: GSOC 2009  

Hello CrystalSpace,
So my exams finished on Friday past and I am now fully committed to the project. My work since then has focussed on reading, I have consumed everything I can find relevant to my project in the hope of solidifying my understanding of CS and CEL before I begin coding.

For anyone following my progress that is concerned about the issues I was having with merging with trunk and the black screen on walktut. These difficulties have been overcome. The merging problem was solved by using svnmerge.py instead of the windows executable provided by the same group. The black screen problems were then solved, with a correct merge to trunk, a fresh checkout of CrystalSpace and the latest (14.02) precompiled version of cswin32libs.

My intention over the next couple of days is to code a few minor self projects, to ensure I fully understand the SCF and current implementation of Quests.

Finally, as some of you will have noticed I have started to lurk on the irc channel whilst working. So if anyone has any questions or suggestions, please feel free to harass me on there. I am still fairly new to irc and not generally used to having message clients running, so I apologise if I am slow to reply but will be very grateful for your input.

Until Next Week, Sam

2009-06-03

Preliminary Work

Permalink 15:23:54, Categories: GSOC 2009  

Hello CrystalSpace Community,
As many of you will know the GSoC 2009 coding period has officially begun and whilst, due to my final exam commitments, I am unable to start full time just yet I have begun some preliminary work on formalising the deliverables for the Quest refactor and setting up my working environment from the CrystalSpace SVN trunk and my assigned CEL branch.

It is my intention to make this blog a weekly update, starting today and continuing every Wednesday throughout the development period to keep the community up to date with the work I am doing.

For now, if anyone has any comments on the existing Quest implementation be they positive or negative please contribute to the CEL mailing list conversation [Cel-main] Quest Refactor . The biggest current issue is to wether we should factor out sequences and instead implement them with a standardised start-finish protocol. Any opinions or comments on this suggestion are greatly appreciated.

I look forward to debating these issues further.
Sam.

2009-04-27

GSOC 2009 Project Proposal

Permalink 13:52:11, Categories: GSOC 2009  

Hello CrystalSpace Community,
I am one of the students taking part in this years Google Summer of Code and am planning to work on a refactoring of the CEL Quest system and implementation of a behaviour tree property class starting on June 1st and working through to the middle of August.

Some of you will know me from my previous discussion of this project during the proposal stages of the programme in the CEL mailing list. During that time a number of other AI related issues were raised and, assuming the success of this project, I still aim to develop some of those ideas further in the future after the GSoC programme closes in August. If anyone would like to discuss AI within CrystalSpace please do not hesitate to email me, irc or comment on this blog, I am very keen to make a continued and succesful effort on this specific aspect of the CEL project.

In a number of recent emails to the GSoC mailing list it has been identified that, for those who were unsuccesful in applying this year, it would be useful if succesful proposals were made available online and so I have attached (a slightly shortened version of) mine below. Partly to aid those applying next year but also to introduce myself and my intentions to those unfamiliar with my project proposal.

I look forward to working with you all and hope to have some more active discussion regarding this project very soon.

Sam.

---

About Me.
My name is Sam Devlin, I am a fifth year computer scientist student about to be awarded a first class MEng in Computer Systems in Software Engineering and beginning a PhD in Reinforcement Learning in October. I have a fond interest in game AI and am looking for a project where I can exert a continuous effort in practical AI throughout my time researching theoretical AI.

I have no current experience working on open-source projects but am keen to learn about this field hence my application to GSoC. I do however have over a years industry experience working on a range of projects for BAE System's. Development during this time was predominantly with C++ using MSVC++.

I have also completed two internships during my undergraduate degree, one of which was within the challenging environment of a major investment bank. The most relevant of which, however, was within the computer science department at the University of York, UK. During this time I worked with a large commercial API to implement modifications, again in C++, to a military simulator. I also gained working experience with Python in the automation of a number of minor tasks.

I am familiar with the OpenGL API having worked with it both during a computer graphics module of my course and in the development of a project for BAE Systems. My experience in AI, however, is more substantial, having focussed a large number of my module choices into this area. I have always excelled in these subjects and as a result was selected to perform my final year project within the AI group. This project involved the use of reinforcement learning under partial observability to make agents play the soccer subgame keepaway. The successful results of my research have been submitted to the IAT'09 conference and have helped me land a DTA scholarship for my PhD research.

My Project Proposal.
Given the current complications and issues with the Quest system (Highlighted at Quest Improvement Proposals, Quest Editor-See Bottom Of Page and my recent discussions on the CEL mailing list.) A number of ideas have been discussed as beneficial to the project and a refactor suggested that removes triggers and rewards from the Quest system and makes them standard property classes available throughout CEL.

In doing this future systems can be designed to take advantage of these powerful tools. An example of this that I propose to implement is behavior trees. Behavior Trees provide similar functionality to FSMs but are considered more intuitive, and make logic more reusable. (For a more detailed argument of Behavior Trees please see: A Behavior Tree Overview)

It has also been argued repeatedly that FSMs are becoming obsolete in industry (For example: FSM Age is Over). If you agree or not, it is important that CS/CEL provide tools for all developers. For those wishing to stick with FSMs the refactored Quest system will be available, and for those who have moved on to behavior trees the new implementation will be available. By implementing Behavior Trees and providing detailed documentation and tutorials it is my hope that the CEL community will begin to explore and develop this technology that is rapidly becoming the industry standard.

<< Previous Page ::

July 2014
Mon Tue Wed Thu Fri Sat Sun
 << <   > >>
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      

Search

Categories

Misc

XML Feeds

What is this?

powered by
b2evolution