ABSTRACT

This work proposes a system design for real time planning for autonomous robots. Implementing a real time autonomous planning agent, which can solve complex problems, is a hard to achieve task where the planning system design must be adapted to process in real time domain and should be able to return satisfactory results.

In this thesis, we aimed to develop a soccer team for robot-soccer competitions. The robotic soccer environment is multiagent and both cooperative and competitive goals are available. We use domain independent planners in order to benefit from their advantages. The first advantage is modularity. It is possible to use the generated system with one or more domain independent planners. The second advantage is the performance improvements obtained with the use of well known and good implemented planners. And another important advantage is the planning system stores the generated plans and can use them in future games.

The planner system is implemented in java and uses the FastForward planner. The implementation was tested in the TeamBots environment against four different teams. The results show that after sufficient number of runs if we store the top requested 1000 plans in the reactive planning module, the Planning Engine returns plans immediately 95 percent of the time which enables our system to behave as a real time planning system. Other statistics show that on the average the number of different plans used in a game is 165 and a maximum 300 plans are used. There is no clear distribution between plan request counts. The number of new generated plans drops in each run and after 300 matches it almost approached 0.

TABLE OF CONTENTS

ACKNOWLEDGEMENTS                            . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                         iii

ABSTRACT                               . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                              iv

OZET¨                             . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                  v

LIST OF FIGURES                              . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                          viii

LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                         x

LIST OF SYMBOLS/ABBREVIATIONS                          . . . . . . . . . . . . . . . . . . . . .                    xi

1. INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     1
2. BACKGROUND . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
   • Planning and Planners . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
     • Progression Planning . . . . . . . . . . . . . . . . . . . . . . . . 4
     • Regression Planning . . . . . . . . . . . . . . . . . . . . . . . . 5
   • Planning with Plan Space . . . . . . . . . . . . . . . . . . . . . . . . . 6
     • Partial Order Planning . . . . . . . . . . . . . . . . . . . . . . . 6
   • Planning Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .         7
   • FastForward Planner . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
   • Time, Schedules, and Resources . . . . . . . . . . . . . . . . . . . . . . 10
   • Conditional Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
   • Execution Monitoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
   • Anytime Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
   • Planning and Acting in Nondeterministic Domains . . . . . . . . . . .      12
   • Probabilistic Planning . . . . . . . . . . . . . . . . . . . . . . . . . . .  13
   • Multiagent Planning Systems . . . . . . . . . . . . . . . . . . . . . . .         13
   • Planning Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . .            14
     • STRIPS Language . . . . . . . . . . . . . . . . . . . . . . . . .     15
     • ADL Language . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
     • PDDL Language . . . . . . . . . . . . . . . . . . . . . . . . . .    16

3. IMPLEMENTATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
   • TeamBots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
   • Representation of the Soccer Planning Domain . . . . . . . . . . . . . . 20

• Soccer Planning Problem File . . . . . . . . . . . . . . . . . . . . . . . 22
• Plan and Team Coordination . . . . . . . . . . . . . . . . . . . . . . .         22
• Plan Commitment, Plan Failure and Re-planning . . . . . . . . . . . . 23
• Overview of the Planning System . . . . . . . . . . . . . . . . . . . . . 24
• System Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . .            25
• Object Model and Database Tables . . . . . . . . . . . . . . . . . . . . 28

4. EXPERIMENTS AND RESULTS . . . . . . . . . . . . . . . . . . . . . . . . 30
   • Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
   • Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5. CONCLUSIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   39

APPENDIX A: SOCCER DOMAIN PDDL IMPLEMENTATION                       . . . . . . .         41

APPENDIX B: PROBLEM FILE 26                            . . . . . . . . . . . . . . . . . . . . . . .                    45

APPENDIX C: PLAN 26                              . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                        47

REFERENCES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                                                        48

LIST OF FIGURES

Figure 2.1.            Progression state space search algorithm [20] . . . . . . . . . . . .              5

Figure 2.2.    Regression state space search algorithm [20]          . . . . . . . . . . . .               5

Figure 2.3.     Initial, goal states, actions of ”have cake and eat cake too” problem

[17] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .                              8

Figure 2.4.    The planning graph of the ”have cake and eat cake too” problem [17]   8

Figure 2.5.     The execution of an execution monitor and replanning agent [17] .    11

Figure 2.6.    Probabilistic version of moving the space from row 1 to row 2 action 13

Figure 2.7.             Joint plan for the double tennis problem [17] . . . . . . . . . . . .            14

Figure 2.8.                  STRIPS definition of travel action . . . . . . . . . . . . . . . . . .                  15

Figure 2.9.                ADL representation of Travel action . . . . . . . . . . . . . . . . .                16

Figure 2.10. Example planning domain                    . . . . . . . . . . . . . . . . . . . . . .                   17

Figure 3.1.          TeamBot simulation environment just after FreeBall . . . . . . . .          19

Figure 3.2.                    Example of a soccer action . . . . . . . . . . . . . . . . . . . . . .                    20

Figure 3.3.          Planner Soccer Domain as extended domain networks . . . . . . .         20

Figure 3.4.     Goal definition of PlannerTeam                . . . . . . . . . . . . . . . . . . .                 22

LIST OF SYMBOLS/ABBREVIATIONS

                                                               1.         INTRODUCTION

Implementing a real time autonomous planning agent which can solve complex problems is a hard to achieve task, since the planning system design has to be adapted to the real time domain. A real time system can be defined as a system which can run in the worst resource and runtime conditions and can produce the best possible results [1]. However, a real time planning agent can not do many of the important needs of real time systems so for the planning domain, we need a less strict definition – A real time planning system will be any system that can return statistically satisfactory results by the required time [1].

In this thesis, the robotic soccer domain was chosen as the real time domain since soccer is the most popular sport of the world with teams of 11 players and millions of fans and robotic soccer is a state of the art testing ground for artificial intelligence (AI) and robotics research with several international competitions like Robocup and FIRA. In addition, robotic soccer requires the joint work of many AI subfields such as vision and planning. Although planning is an important subfield of AI it was not widely used in the robotic soccer due to the real-time nature of the domain. However, with the advances in the planning algorithms and the processing power available on the robots, it is now worthwhile to asses the feasibility of integrating planning systems with autonomous robot systems and make them play robotic soccer.

Many teams from all over the world are developing autonomous robots for competitions. Some of the leagues demand more hardware and software processing and some of them are on simulation environments. It is rather easy to develop simulation robots and AI systems make difference between teams. In this thesis we focus on the AI of the autonomous robots. In these competitions, some teams use mathematical models for robot behaviors where robot behaviors are specified through differential equations [2]. Case-based reasoning is another approach for selecting actions [3]. Logic based high level agent programming languages are also used [4]. Behavior based approaches are more common [5], sometimes with dynamic role allocation [6]. System life based approaches are also used [7]. Feedback controllers [8] and fuzzy logic based behavior systems [9], finite state machines [10] are frequently employed. Multilayered reinforcement learning is used frequently, e.g. [11].

Different from these approaches, the motivation behind this work is to explore the possibilities of real time planning systems and find ways to integrate classical planners to the real time planning environments. The continuous effort and the performance improvements on classical planners motivated us to explore the ways to use classical planners with autonomous robots.

Besides, we think that we can benefit from the possibility of future performance and functional improvements over classical planners. Planners are generally used in static domains whereas we aimed to use our system in soccer domain which requires team coordination, role assignment and synchronization.

The thesis is organized as follows; the next chapter covers the background information on planning, the FastForward planner and the Teambots simulation environment. The Chapter 3 covers the details of implementation and all the classes are explained in this chapter. In the Chapter 4 experiments are described. The results of the experiments are stated in Chapter 5. The concluding remarks are given in Chapter

DOWNLOAD THE FULL WORK

DISCLAIMER: All project works, files and documents posted on this website, UniProjectTopics.com are the property/copyright of their respective owners. They are for research reference/guidance purposes only and some of the works may be crowd-sourced. Please don’t submit someone’s work as your own to avoid plagiarism and its consequences. Use it as a reference/citation/guidance purpose only and not copy the work word for word (verbatim). The paper should be used as a guide or framework for your own paper. The contents of this paper should be able to help you in generating new ideas and thoughts for your own study. UniProjectTopics.com is a repository of research works where works are uploaded for research guidance. Our aim of providing this work is to help you eradicate the stress of going from one school library to another in search of research materials. This is a legal service because all tertiary institutions permit their students to read previous works, projects, books, articles, journals or papers while developing their own works. This is where the need for literature review comes in. “What a good artist understands is that nothing comes from nowhere. All creative work builds on what came before. Nothing is completely original.” - Austin Kleon. The paid subscription on UniProjectTopics.com is a means by which the website is maintained to support Open Education. If you see your work posted here by any means, and you want it to be removed/credited, please contact us with the web address link to the work. We will reply to and honour every request. Please notice it may take up to 24 – 48 hours to process your request.