-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathprogress.log
164 lines (136 loc) · 14.9 KB
/
progress.log
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
Jun 8, 2009:
Using pygame to set up a basic drawing area and World instance.
Have a Unit moving back and forth across the empty screen.
New main classes: World, World.Pos, Unit
Testclass: Stupid(Unit)
Todays reading (excluding API lookups):
Pygame documentation
Python metaclasses
Jun 10, 2009:
Setting up algebra for python. Looking into NumPy package
Jun 11, 2009:
Improved Position class (separated from World)
Jun 12, 2009:
Put Position class into separate file
Working targetsystem for Units (World moves units according to their decisions)
Created RandomWalker Unit to walk around randomly. (demo)
Created Bouncer Unit to walk back and forth. (demo)
Rendering of path to target
Still no collision detection, but sketched up some ideas:
(for optimization)First check if the rectangle that a unit moves through intersects a rectangle from another units movement
If so, do a robust check to see if, and with what force the units collide and record this data.
Should also move units apart where they collide (i.e. not be possible to move through other units)
For system performance check, a simple FPS viewer is available. It needs some improvement though :
Average over time to account for big differences with short iteration times
Jun 13, 2009:
Exchanged own Position class for Pygame inofficial vec2d-class which is more python-complete and well tested
Jun 15, 2009:
Ideas:
Planning, Physics, Rendering could be different modules
But planning and physics would probably have to be synchronized/same thread to give repeatable results
Jun 16, 2009:
Reading more python docs. Using itertools
Jun 17, 2009:
Refactoring design pattern to have better data encapsulation and protection.
Jun 23, 2009:
Rethinking Unit/Intelligence/Physics design pattern.
Intelligence should not be able to directly set the position or other properties controlled by the physics engine directly.
As a result of this, the data passed to the intelligence should either be copies of the internal data, or immutable versions of the same (the latter is hard to achieve).
In short: the internal datastructure holding physical properties of the object should never be exposed to the intelligence. In python, complete data security is practically impossible, but it should at least be apparent that physical properties should not be altered directly.
Options:
#1 Having a Unit class that contains both physical properties, intelligence and unit drawing. Creating a deep copy of the instance before calling the "think()"-method on the newly created instance, securing any data in the internal Unit-class for the physics engine to use.
This still exposes a "fake" unit to the intelligence.
Pos: Everything about a unit is packaged together
Neg: Thinking object (Unit) is not retained between think()-calls, making it hard to save data between calls.
#2 Having separate Unit and Intelligence objects for each thinking entity. Physics data sent as argument to Intelligence when calling think()
Pos: The Intelligence instance can be retained between calls. More apparent that physics data are read-only.
Neg: Added complexity to the system. More code.
On second thought option #2 seems to be by far the best looking and structurally correct option, so I will go with that.
Physics state:
Should unit state (i.e position, velocity, forces etc.) be encapsulated even further? Allowing physics model to be changed to using matrix oprations rather than multiple vectors.
Should this state be encapsulated in the Unit class or in another structure owned or inherited by the Unit class?
Created State class for benchmarking numpy array,matrix vs. pygame inofficial vec2d. Numpy matrix was slower, numpy array was faster (when should you ever use matrix?)
Summary of plan:
Unit - View in MVC pattern, holds informations such as a units color and drawing code (which gets access to physical state too when drawing).
State - Model in MVC pattern, holds physical properties of object that in any way affects how the physics engine works on the object.
Optionally: PublicState - Special state object that exposes only certain physical properties for other parts than the physics engine to see
Intelligence - Controller in MVC Pattern. Has the think(WorldData data) method that takes certain public properties of the rest of world as a parameter, and can issue orders of changed behaviour for the object to the physics engine.
Engine step:
So far the engine has been coded like a game: Draw frames as fast as possible and maintain real time syncronisation.
For scientific purposes, this is not optimal - the results will vary depending on the hardware where the system is run.
A better aproach would be to emulate a fixed framerate and send in the same time step for every frame. This way, the system will run equivalently every time (except if seeded "random" is used) allowing exact repeatability - the basis for empirical science. How this time step is determined is not very important, but could be chosen in a way that makes real-time display of simulations go at a pleasant speed. Also, collision detection could be made much simpler by choosing a small enough time step so that objects never can "pass" each other by accident and a simple bounding box/radius-comparison will suffice for basic collision detection.
Jun 29, 2009:
C++ physics module written and added to projekt to allow fast simulations even with many units.
Ai will still be written in python for simplicity, and possibly ported to C++ if performance is not sufficient.
think() is supplied a tuple containing all particles within a units range
Jul 7, 2009:
People avoid each other now but are still quite stupid.
Carson suggests adding acceleration to the system. Possibly turning-speed too.
Can you trust people to avoid robot?
- Depends on size and "camouflage" of robot. Does it nessesarily look like a human? Is it possibly smaller like a dog? Does it move to fast for people to notice it and does it make noise?
Will probably make robot somewhat hard to avoid for people, to give greater responsibility to robot. Otherwise the project will transform into a human movement research problem.
TODO: Add obstacles to system. Polygon based? Needs to be added on the C++ side for collision detection etc.
At the moment the system is performing really well in terms of framerate. The thing that takes by far the most time is rendering, which is still done in un-accelerated pygame.
TOPONDER: Emulated time and minimum frame per time unit? Set frame rate in emulated time?
Anytime planning. Set frame rate should only affect physics/drawing part. Think()ing must still be done as fast as possible. Otherwise, algorithms will not be able to take advantage of having a fast iteration speed by being able to update targets more often.
Jul 9, 2009:
Reading the following papers:
Jan Rosell, Pedro Iniguez
Path planning using Harmonic Functions and Probabilistic Cell Decomposition
David Hsu, Jean-Claude Latombe, Hanna Kurniawati
On the Probabilistic Foundations of Probabilistic Roadmap Planning
Maxim Likhachev, Dave Ferguson, Geoff Gordon, Anthony Stentz, Sebastian Thrun
Anytime Search in Dynamic Graphs
Jul 14, 2009:
Implemented Dijkstra for simplicity. Tried making simple changes to transform it into an heuristic-based A* but realized that A* not always uses consistent heuristics, so will have to refactor the implementation a bit to get it to work with inconsistent heuristics.
Constructed test case of a graph with inconsistent heuristic that breaks my first implementation of A*.
Later: Implemented proper A* that works (as far as I have tested) with inconsistent heuristics.
Jul 16, 2009:
First A* integrated into the simulator. Right now uses a randomized graph within the viewing range of the robot and updates the path for every step in the simulation, which is a bad combination as it makes the robot use a lot of its time for rotating on the spot when changing course. This brings up the problem of using distance for the measure of the A*. What should really be minimized is the time to reach the goal. This would include robot orientation as well as position in the state-space - making the graphs a lot bigger, depending on implementation.
After some thinking and discussion with Carson Reynolds, I am leaning to a solution of having 2*N different orientations for each of the positional nodes in the current state graph where N is the number of positional neighbors to the current node. Each of these nodes would correspond to a direction to or from a neighbouring point and these nodes would be connected to each other (with the cost being the time it takes to rotate between states) and to the nodes they "point to" in the spatial state space. This will "only" increase the state space by a factor of the average connectivity of the graph but the connectivity of the new graph would likely be lower (some more in-depth analysis could be interesting).
When the searched graph grows python gets increasingly slow at searching it using A* and this severely impacts performance of the whole system so I am considering "outsourcing" A* and a few other graph-related functions to C/C++ as has already been done with the physics engine.
Jul 22, 2009:
C++ optimized A* done. Proper Probabilistic Random Planning (PRP) implemented. Very short development time. Results are quite good but in urgent need of something that penalizes turning time.
Todo for the coming days:
- Turning time part of A* search
- More intelligent crowd that actually has goals and possibly reacts with environment more
- Some form of minimal time step for physics engine updating. Units should not be able to skip through each other because things gets slow. "Set frame rate" probably good idea but there should be some form of punishing longrunning algorithms as well. Possible solution: Run physics engine at set frame rate (say 30 fps) in real world (most computers should be able to do that, at least without rendering). Run a lower prioritized thread/process for the unit we are tracking so the number of iterations it can do is inverse proportional to it's average iteration time. This way there will be a fair measure of comparison as long as the tests are performed on the same system. Timing for the robot to reach it's goal will also be easier.
Jul 27, 2009:
Successfully prototyped graph generator (class GraphBuilder) for building search graphs which has both orientation and position as state variables. To build this graph efficiently, only possible ways of orientation for the robot are stored at each position, i.e. the directions of adjacent nodes.
Preliminary efficiency tests show a gain of approximately 10%-20% when robot turningspeed is set to 2*pi/3. Expectation is that the higher the turning speed, the lower the gain. Comparison was done using same random seeds and a set time step for each iteration. Iteration time has not been measured yet, but is assumably a bit worse but in the same order of magnitude.
Made rendering optional in the engine, so runs can be made faster if only looking at statistics.
Todo:
- Improved repeatability. Set time steps. Measure world time/number of iterations, real time, and from this => average iteration time.
- (From before) More intelligent crowd.
- A*:ify GraphBuilder (uses heuristic = 0 at the moment => Dijkstra), if only for better slightly lower runtime/average iteration time.
- C++ify GraphBuilder (right now takes a bit of time)
- Recorder - Save test runs. Could be saved by saving all the intermediate states, or just the random seed used.
- Keep statistics. Save statistics including revision of project and system used.
Jul 28, 2009:
Some refactoring of physics system. Recording more stats now. Displays runtime, world time (which is a separate measure now), collisions and average iteration time. Still a lot work needed to be done in this aspect. And recording this to database/statistics files would be good to be able to follow progress.
Observations:
- I am not sure the new "turning" A* works exactly as expected even though it obviously gives better results than previous approaches. The prototype needs to be examined closer.
- When adding many points to the random roadmap simulations go slow. Unnecessarily so. Easy to port to C++ and should be.
- Would be interesting to add a "human" robot to get an estimation of how good humans would be at the same planning. My hypotheses is that a human that get sufficient time for each time step would be more effective than the current implementation because it does not account for likely movements of units later in time.
- This brings me to the next point: Creating an AI that efficiently navigates using other units likely movement to avoid future pileups of crowd members etc.
- Crowd still needs to get more realistic to actually get something out of this. Should create some kind of repeatable "scenarios", possibly with rigid obstacles that the different strategies can be evaluated in.
Aug 3, 2009:
Reading paper on Path planning using harmonic functions and probabilistic cell decomposition.
Got some inspiration for a "dynamic" A* using randomly expanding trees in space-time statespace to avoid future probable collisions.
Scenarios can be chosen at launch using terminal parameters. Feature to create: GUI for launching simulations and saving results in a database.
January 2013:
Refactored a bunch of things and found several implementation mistakes in Arty code. Made some optimizations and created new scenarios.
Insights:
- Global graph isn't optimized for time to goal, but time to connected node when being built. Optimizing for time to goal is probably beneficial.
- There is a lot of branch-cutting heuristics in arty that would make the algo better if they were removed, but also slower:
* Using trees instead of directed acyclic graphs for both local and global search. Makes implementation simpler and less computationally intensive though.
- Intersection between pedestrian and agent can probably be postulated as a non-linear optimization problem. Right now it's essentially being solved by suboptimal brute force, but it can probably be much faster using established optimization techniques.
- Can probably improve performance of pedestrian collision detection by first trying time-independent line-intersection of movements from both actors, that should give us some false positives (for collision), but will eliminate o lot of work for all the (true) negatives it will provide.
January 6th 2013:
- Maybe it's better to generate very sparse global graphs (or at least remove extraneous points after generation) to just have some helper points for difficult topologies.
Then we can use local search to its full extent every iteration and navigate to the best point in the global graph (the closest one to the target which is safe) every time. This is probably a good idea.
- Parameters to Arty should be:
* int: agent_min_nodes (for agent graph), before trying to find goal graph
* int: agent_max_nodes (for agent graph), before giving up (this could also be time based...)
* int: goal_nodes
* boolean (default true): stop_on_closest, stop checking global nodes when one approximately closet to the goal has been found