Dr. G. Bernat. Student Projects 2003-2004
To be chosen in 2003.
To be taken in 2003-2004
These projects are related to either the Robot football team project
or Worst-case Execution time analysis. The projects are
suitable for MEng, CS or CS/Maths students. Projects GB/8-GB/10
are also suitable for MScIP students. Please refer to the project
allocation database for details.
If you have great idea of a project that you think I could supervise,
contact me.
Robocup:
The York robocup team is an initiative to build a team of small
autonomous robots that play football. See the York robocup page for
details of the current projects and documentation.
GB/1- Real-Time Object Tracking for Robocup.
[MEng,CS,CS/M]
The purpose of the project is to use the result of the first stage of
the vision system to identify and classify the objects in the playing
field.
The first stage of the vision system produces every 25 ms a description
of colored regions in the playing field. This may correspond to the
markers of the robots, the ball but also to noise in the enviroment,
walls in the goals etc.
The aim of the project is to use predictive algorithms and filtering
mechanism to track and predict which objects really correspond to robots
and balls as well as to extrapolate their position in the case that a
frame is not processed on time. Evaluation of Kalman Filters [1,2]
[1] Kalman, R. E. (1960). A New Approach to Linear Filtering and
Prediction Problems, Transactions of the ASME – Journal of Basic
Engineering, 82(D),
35-45.
[2] Zheng Wang, Bernhard Hengst, Claude Sammut. "Localisation in an
Uncertain World with Multiple Agents".
http://www.ida.liu.se/ext/epa/cis/2002/019/cis02019.html
GB/2- A kicking device for Robocup (student defined)
[MEng,CS,CS/M]
Background
The Robots in the York Robocup Team [1] at present can push a ball but
not kick/dribble it. A solution to this problm is required.
Aim
The aim of this project is to Model, design, implement and evaluate a
kicking device for a robot in the robocup team.
Modeling the system would involve taking into account how a ball would
respond under certain conditions and how to manipulate the ball based
upon analys of ball games.
Design will involve playing with several concepts and composing them
into several ideas. Analyse several ball games and see how humans
control balls. Then filtering them out and producing a solution to the
problem. A set of diagrams shall be produced for someone else to
manufacture.
Implementation shall be asembling the solution together with eletronics
that has been built to control various parts of the physical hardware
developed.
Evaluation will be testing the solutions to see how they perform under
the following tests. Kicking the ball, dribbling the ball, rotating the
robot with ball under control.
Involves:
The project may involve:
Low level programing
Electrical hardware design and building
Physical hardware building
Mechanical Mathamatics
Design work
References
[1] http://www.cs.york.ac.uk/robocup/
Probabilistic Worst-Case Execution Time Analysis.
The rest of the projects are on the area of determining the longest
execution time of embedded real-time programs. The projects complement
and extend current tool support. Research opportunities may arise after
these projects.
Common references for the rest of the projects:
GB/3- Using POSIX Tracing and RT-Linux for timing
analysis. [MEng,CS,CS/M]
The aim of this projet is to reconstruct the path that a program takes
to execute together with the time it takes to run. The approach is to
use the subset of the RT-Linux implementation of the POSIX Tracing
standard and use it to automatically build execution traces.
The project involves
- Configuring and installing RT-Linux and
the Posix Tracing support.
- Manually instrumenting a set of case studies
following the POSIX tracing standard
- Implementing a trace analysis mechanism that converts
these traces and determines execution times of blocks of code
- [1] Posix Tracing
in RT-Linux
- [2] A. Terrasa, G. Bernat "Extracting real-time
properties from real-time systems by automatic trace analysis". IEEE
Real-Time Computing Systems and Applications Symposium RTCSA,
Taiwan, February 2003.
GB/4- Automatic instrumentation of Ada programs for
Execution trace generation. [MEng,CS,CS/M]
Automatic tracing analysis requires the code to be instrumented with
calls to a tracing library. The execution of the instrumented program
produces an execution trace that can be analysed by the pWCET tool.
The programs have to be instrumented at each control flow decision
point so that the exact path can be determined.
The purpose of this project is to automatically instrument Ada 95
programs using a predefined instrumentation library. The tool should
also report the instrumentation performed and allow a
"deinstrumentation" of already instrumented code.
(See GB/5)
GB/5- Automatic instrumentation of C programs for
execution trace generation. [MEng,CS,CS/M]
Automatic tracing analysis requires the code to be instrumented with
calls to a tracing library. The execution of the instrumented program
produces an execution trace that can be analysed by the pWCET tool.
The programs have to be instrumented at each control flow decision
point so that the exact path can be determined.
The purpose of this project is to automatically instrument C
programs using a predefined instrumentation library. The tool should
also report the instrumentation performed and allow a
"deinstrumentation" of already instrumented code.
(see GB/4)
GB/6- Automatic annotation extraction in Ada programs.
[MEng,CS,CS/M]
The tool for performing worst-case execution time analysis requires
additional information of the timing behaviour of the programs in order
to provide tight estimates of the execution time. These include;
- Maximum number of iterations in loops
- Mutually exclusive paths
- Dependencies of loop bounds in nested loops
- Parameterised function calls
This extra information is included as annotations in the code, for
example as simple as:
for i in 1 .. 10
loop --# maxiter(10)
do_something;
end
loop;
The purpose of the project is to automatically extract the annotations
from the source the code and map them to the already parsed
structure of the program (an XML representation of the program)
generated by the pWCET toolset. The challenge of the project is that the
structure of the program is obtained by the analysis of the object code
generated by a compiler. This structure does not necessarily have a one
to one mapping with the source code due to the transformations made by
the compiler optimisation process (which are not known).
The project involves the construction of such a tool and the
evaluation through a series of real-life case studies.
(See GB/7)
GB/7- Automatic annotation extraction in C programs.
[MEng,CS,CS/M]
The tool for performing worst-case execution time analysis requires
additional information of the timing behaviour of the programs in order
to provide tight estimates of the execution time. These include;
- Maximum interations in loops
- Mutually exclussive paths
- Dependencies of loop bounds in nested loops
- Parameterised function calls
This extra information is included as annotations in the code, for
example as simple as:
for
(i=0;i<10;i++) //# maxiter(10)
{
doSomething();
};
The purpose of the project is to automatically extract the annotations
from the code and map them to the already parsed structure of the
program (an XML representation of the program) generated by the pWCET
toolset..
The purpose of the project is to automatically extract the annotations
from the source the code and map them to the already parsed
structure of the program (an XML representation of the program)
generated by the pWCET toolset. The challenge of the project is that the
structure of the program is obtained by the analysis of the object code
generated by a compiler. This structure does not necessarily have a one
to one mapping with the source code due to the transformations made by
the compiler optimisation process (which are not known).
The project involves the construction of such a tool and the
evaluation through a series of real-life case studies.
(See GB/6)
GB/8- A Java based GUI for visualisation of the
structure of programs. [MEng,CS,CS/M, MScIP]
The pWCET toolset analyses programs and builds a syntax tree
representation, called XST (extended syntax tree). An XST is an XML file
that contains in a tree representation the source program, links to the
object code, and extra information for the pWCET analysis. The purpose
of the project is to create a graphical user interface to nicely
represent and browse these data structures.
The aim of the project is to create a GUI for displaying this
data and to allow the interaction and navigation of these structures.
The tool should also provide the usual features of a GUI, printing
support, navigation, etc.
GB/9- A GUI for visualisation of execution profiles.
[MEng,CS,CS/M, MScIP]
The result of the probabilistic WCET analysis of a program is the
probability distribution of the execution time of individual sections or
blocks of programs (See reference [1] above). These blocks can be as
small as few instructions or as large as whole programs.
The visualisation and comparison of such profiles is essential for
the evaluation of the timing behaviour of the program. In
particular the level of probability can be very small and therefore
alternative ways of plotting the distributions (mainly logarithmic
plots) are required
The purpose of the project is to develop a standalone application that
is able to display profiles with advanced customisation features, zoom
support, printing support etc.
GB/10- A java XML toolset for program structure
analysis. [MEng,CS,CS/M, MScIP]
The pWCET toolset extracts the syntax tree of the program and builds an
XML representation called XST (See GB/8). The user also
annotates the program with code annotations(in the form of comments)
that provide extra information of the temporal behaviour of the program,
like maximum number of iterations of loops, as well as operations on the
tree.
The purpose of the project is to build a script based application that
is able to manipulate the XML tree representation. The input of the tool
is an XST and a set of operations on the tree and the result is the
modified tree.
The list of potential operations to implement are:
- Display a node or a range of nodes
- Remove a node and all its descendants
- Add a new node
- Find a node according to certain criteria
- Attach annotations to particular nodes
- Renumber the identifiers of a node
- Update the information of a node
- Clone a subtree
- Move a whole subtree
- etc...
|
|
|
