License

See the LICENSE file in the repository.

Overview

This repository contains the assignment submitted for evaluation, based on a specification provided. The overall goal is to simulate a drone, a ground control station, and the communication between these two entities.

No AI has been used in this repository.

Setup and Build

Building has been tested on Ubuntu LTS 24.04, using g++-14. The system default of g++-13 does not support the <print> library. The following system packages are required, as they are needed to get the assignment provided CMake to work:

sudo apt install -y build-essential cmake pkg-config libpkgconf-dev g++-14 gcc-14
sudo apt install -y libgl1-mesa-dev libglu1-mesa-dev freeglut3-dev mesa-utils mesa-common-dev libglew-dev libglfw3-dev libwayland-dev libxkbcommon-dev xorg-dev

Project can be downloaded, configured and built as follows:

git clone --recurse-submodules https://git.skullnet.me/erki/kratt-test-assignment.git
cd kratt-test-assignment
export CC=/bin/gcc-14
CXX=/bin/g++-14
cmake . -B./build
cmake --build ./build --config Release --target all

Build Flags

Some flags were added to the cmake to allow for better debugging and error detection.

• To build all applications with address sanitization, pass -DWITH_SANITIZERS into the initial cmake command.
• To build all applications with -Wall -Wextra flags, pass -DWITH_EXTRA_WARNINGS into the initial cmake command.

An example with full flags: cmake . -B./build -DWITH_SANITIZERS -DWITH_EXTRA_WARNINGS

Tests

The core library is tested. This covers tests of the drone simulator, UDP communication, UDP proxies, etc.

After building per above instructions, these tests can be ran with the following commands:

./build/shared/kratt_shared_tests

Source code wise, all tests are located within the shared/test folder.

Running the Apps

None of the applications accept arguments.

The ports used are 9050 - 9053, inclusive on both bounds. All sockets will bind to 0.0.0.0.

To run the drone application, build per the above instructions and simply run ./build/Drone.

To run the GCS application, build per the above instructions and simply run ./build/GCS.

Note regarding GCS: Due to the way GLFW event polling works, the application will not work properly if you defocus the window. This is due to the GLFW event polling architecture not letting the main loop run while the window is being adjusted or defocused, and thus the incoming message pipes from the UDP channel not being read. The UDP channel and proxies themselves will keep operating in the background, but the UI won't respond.

In theory, the application should recover after you refocus on the window and let it run for a bit. It'll clear up the message queues and you're good. This issue would be prevented by using a non-polling event handling system in the UI thread.

Architecture & Solution

Project Structure

The project is structured as a single shared library, and 2 different final applications.

The goal behind building a large shared library is to allow the final applications to share common code, and to make testing easier. The testing for example covers the whole UDP communication stack (being a mix of both unit and integration testing).

Final application code is thus kept simple enough, minimizing the amount of testing necessary.

UDP Communication

UDP communication uses the assignment provided SimpleUDP library with non-blocking operations. The main workhorse of the UDP stack is the kratt::channels::udp class, found in shared/inc/kratt_shared/udp_channel.hpp and shared/src/udp_channel.cpp folders.

A channel in this case represents a 2-way, point-to-point UDP data channel. The channel communicates with the rest of the application via 2 thread-safe queues. In the outgoing direction, the application can give the channel messages to send. In the incoming direction, the UDP channel will provide incoming messages, statistics, and up-down events (unless the channel is stateless). Because the queues are thread-safe, the UDP channel can be moved into a separate thread just fine.

Assumption made: the communication is point-to-point. Anything else would exceed allotted complexity.

Queues

Message queues like this are a good way to decouple a channel implementation from the code using it. The code using the UDP channel can be refactored to simply expose its message queues, and then it can be fed messages for testing purposes. Alternatively, since the queues become the interface, the UDP channel can later be replaced with whatever other communication interface, as long as it accepts the message queues.

An illustration of how message queues are used to break a dependency on the threading and the communication method is shown in the gcs_application class in src/gcs_application.cpp. The class has its own message queues, and main() wires them up to the UDP channel without the application class itself having to worry about it.

Messaging

The messages themselves are managed by the MAVLink library. We simply let mavlink pack the data, and use its own framing, formatting, CRC, sequence numbering etc. This gets us a good datagram data content easily enough, gets us error detection, etc. While maybe wasting a few bytes.

Assumption made: MTU size is large enough to contain the worst case MAVLink message, being ~300 bytes. If the size is too small, and we have to deal with data fragmentation, then MAVLink's framing might not suffice: there's no way to reorder a fragged and misordered package (consider that the ordering from UDP is potentially unreliable). Although I also suspect that the "UDP" from a radio isn't necessarily similar in characteristics as UDP from a wired network is.

Delivery resilience is also handled by the channel class, using optional automatic repeat request. When giving a message to the UDP channel class, you can mark it as expecting a reply in the form of a specific MAVLink message ID. The UDP channel will keep resending the message every 15 ms until the sender responds with a reply of that type. While repeating the message, the sender will happily also accept other messages, as they may already have been inflight before the marked request was sent.

15 ms as the retry timeout was chosen due to the maximum bandwidth of the link, and the maximum length of a MAVLink message giving us a total transmit time of ~12 ms, in the worst case.

While trying to resend the same packet, the sender will not send new packets. Ergo, if the rest of the application keeps giving it messages while it hasn't gotten a response from its original marked request, the send queue will fill up eventually and packets will be dropped.

Any more sophisticated algorithm (like a sliding window) doesn't seem reasonable given the relatively low bandwidth in play.

Testing

Tests can be found in the shared/test/udp_channel.cpp file, and also in the proxy's shared/test/udp_proxy.cpp, and shared/test/udp_proxy_double_sided.cpp files.

In all test files, an integration test with two channels talking to one another and experiencing packet loss is ran.

Proxy

The proxy acts as a man-in-the-middle between two UDP channels. Located in shared/inc/kratt_shared/udp_proxy.hpp and shared/src/udp_proxy.cpp files.

As per assignment specification, it will delay packets based on their length and link bandwidth of 32 KB/s. It will also cause simulated packet loss by not transmitting packets based on an assignment packet loss percent. Inside, it functions as a simple queue, doing work based on the system clock.

Simulator

The simulator acts as the drone's movement simulator.

Assumption made: For the sake of simplicity, I've contained the drone to an area of 100 x 100 metres. Starting from a coordinate of 0, all the way up to 100. Altitude is also locked to 10 metres, and acceleration is instantenous.

The drone simulator has a maximum speed of 1 m/s. Based on its current location and the target destination, the simulator will simulate the drone heading towards its target and the fixed speed. The simulator provides functions required to populate the MAVLink messages specified for use.

Threading and Work

Due to the provided libraries not providing sufficient tools for OS-specific/OS-abstracted event loops, a simple "do a bit of work, sleep" model was used. Something you may find in a microcontroller based environment. Ideally this would be reimplemented using epoll, select, or something similar, assuming the target remains a system with an OS; interrupts and event flags otherwise.

All classes that need to do regular work implement a run_some() function, which has to be called regularly. All classes implementing this function make sure to rely on the system clock to figure out what they have to do, instead of assuming a specific calling frequency. This minimizes mistakes later on.

Given the various requirements and limitations of the specification, the highest frequency for this would be the UDP channels. But even there, calling run_some() every milliseconds is sufficient.

What's more interesting, given the requirements and limitations of the specification and the nature of the UDP library, it isn't actually necessary to move the UDP channel into a separate thread for the Drone application. Since the sending and receiving is non-blocking, the channel's run_some() can simply be called in the main thread alongside everything else.

The proxies and the UDP channel in the GCS application are given their own thread, to ensure that the UI event polling issue mentioned in the beginning does not cause the UDP messaging to stop working.