Personal Timetabling – Bachelor’s thesis

Abstract

Despite all the advancements in Artificial Intelligence, we still do not have a broadly available application for automated scheduling of personal activities. The main difficulty in creating such an application is satisfying user’s diverse expectations about time organization. In this study we focused on creating a tool that can help users with organizing their time. We designed a model for describing personal activities with user preferences. We formulated scheduling of personal activities as an optimization problem for which we designed and implemented a solving algorithm, aiming to schedule activities with precision of seconds.

We created a prototype of web-calendar application powered by this model and an algorithm which we designed with the focus on ability to clearly display user’s time and easily insert activities for automated scheduling. The web application is backed by RESTful API which enables implementing application on various platforms.

Preview

Personal Timetabling - adding new request Personal Timetabling - solving Personal Timetabling - example calendar

About

How it works

Instead of placing tasks to fixed time as you can do in classical calendar, here you have to in what time window you want to do that task. This information is then available for all tasks in calendar and so when you want to add new one, it was searched how other tasks can be reorganized in order to make time for the new one. During search it is trying to maintain time of already scheduled tasks.

It uses variation of local search techniques used in artificial intelligence field.

Technologies

I wanted to use the right technology for every part of the software. So user interface is done purelt in JavaScript with use of Backbone.js library. Server interface was build in Ruby on Rails and core algorithms was written in Java. Connection of these technolgies to work together was quite a challenging but I managed to make it.

Download

Personal Timetabling thesis (PDF, in czech)

Project on GitHub

Generování kalendáře v XSLT 1

XSLT se normálně používá pro transforamce XML dat ve smyslu jejich různého obalení (např. do HTML), přeskupení, vytažení nebo seskupení na základě různých kritérií. Umí toho ale podstatně více. V XSLT se totiž dá naprogramovat de facto jakýkoli algoritmus.

Tento příspěvek se bude snažit ukázat, jak této vlastnosti XSLT využít pro následující dílo :)

XSLT calendar

Na úvod

V rámci cvičení k přednášce XML technologie na Matfyzu jsme měli za úkol vytvořit nějaký netriviální XSLT skript.
Jako data jsem si vzal XML popis rozvrhovacího problému, které mám z práce na bakalářce a říkal jsem si, jak bych je mohl prezentovat. Řekl jsem si, že bych mohl zkusit vykreslení kalendáře (klasického měsíčního s řádky po týdnech) se znázorněním časových oken ve dnech.

Na první pohled se může zdát, že na tom není nic extra. Je třeba si ale uvědomit, že zdrojová data žádnou informaci o kalendáři neobsahují a jak už jsem zmínil na začátku, XSLT je navrženo pro zobrazení existujících dat. Zároveň budu chtít vyhodnocovat, jaká okna jsou v jakém dni a to pouze na základě logických podmínek zapsaných v datech – tedy nikde není seznam dnů, ve kterém by okno bylo aktivní (může jich být dokonce nekonečno).

Když jsem se tedy do psaní XSLT skriptu pustil, začal jsem v XSLT 2.0 a šlo to celkem pěkně. Pak jsem ale zjistil, že na domací úkol to musí být v XSLT verze 1 a tak se podělím i o tom, jaké zapeklitosti přináší první nebo druhá verze.

Struktura dat

Podívejme se nejprve na XML soubor, který bude předmětem transformace. Datový XML soubor je opravdu jedonoduchý popis rozvrhování aktivit. Obsahuje

  • definice časových oken
  • definice kategorií aktivit
  • a samotné aktivity určené k rozvržení

Pro účel tvorby kalendáře budu pracovat pouze s časovými okny. Jejich podoba v XML je následující:

Z toho bude pro kalendář důležitý především element pravidla. Ten obsahuje podmínky, které když všechny platí současně na určítém datu, tak v to datum je okno dostupné. Podmínky (dle aktuálního schématu viz příloha) mohou být:

  • porovnání s konstantním datumem (větší, menší, rovno) (element den)
  • datum je pracovní den (element pracovniden)
  • porovnání s pořadím dne v týdnu (element denvtydnu)

Implementace skriptu

Popíši zde pouze zajímavé části skriptu, který je na konci příspěvku k dispozici ke stažení.

Výpočet dne v týdnu

Výpočet čísla dne v týdnu lze řešit mnoha způsoby (viz Determination_of_the_day_of_the_week). Já jsem použil Gaussovu metodu, na čemž není nic až tak složitého. Zajímavé na tom ale je, že to ukazuje sílu XSLT jako programovacího jazyka a že se v něm dá napsat i složitejší matematický výpočet.

Na tomto příkladě bych ale chtěl prezentovat hlavní rozdíl mezi XSLT 1 a XSLT 2. Podívejme se na rozdíl:

Nejprve hezčeji v XSLT 2:

a nyní v XSLT 1:

Všimnout si můžete 2 rozdílů:

  • funkce se v XSLT 1 nejmenují funkce, ale šablony
  • v XSLT 2 je datum předáno jako typovaná hodnota data, zatímco ve starší verzi jako 3 samostatné části den, měsíc a rok
  • výsledek je v XSLT 1 “plácnut” jako výstup šablony, v XSLT 2 je to typovaná a přesně ohraničená hodnota

Především to, že v XSLT 1 ještě funkce nebyly zavedeny, způsobuje značné množství textu kolem. Není to totiž nic, co by nešlo udělat, ale je s tím zbytečná práce – volat šablonu, předat ji parametry, navrat uložit do proměnnév (to zde není, ale představte si, že okolo volání posMod je ještě element xsl:variable), tu pak použít dá na 3 vnořené XSLT elementy. V XSLT 2 je to název funkce uvnitř XPath výrazu.
Významnou nevýhodou starší verze XSLT je také absence datových typů a s tím související absence pokročilých vestavěných funkcí. V tomto případě jsou vhod funkce pro práci s datem.

Generování tabulky kalendáře

Právě výpočet dne v týdnu se bude u kalendáře hodit. Stačí pak totiž vzít kolikátý den v týdnu je prvního v měsící, na takovém sloupci začít a pak už jen přičítat den s vypsáním buňky, když je neděle (resp. sobota u anglického týdnování) vložit nový řádek a tak dál dokud není konec měsíce. Jednoduché, že?

Alespoň takhle, by se to udělalo narychlo v PHP, C#, či jakémkoli jiném procedurálním programovacím jazyce. Jenže v XSLT nelze říct “opakuj dokud”, “vypiš když” a to především asi proto, že nelze říct “přičti den”. Proměnné v XSLT jsou totiž jen deklarativní a ve skutečnosti se chovají jako konstanty. XSLT je tak v tomto směru mnohem blíže např. prologu.

Jak tedy na to? Kdo zná neprocedurální programování už asi tuší. Cestou je rekurze. Jedinou možností jak změnit proměnnou je, jak jsme si řekli, právě její nastavení. A nastavit jde například při volání funkce (resp. šablony). Vytvoříme tedy šablonu, kterou chceme opakovat a při každé iteraci mít jinou hodnotu proměnné. Tu pak v ní samotné voláme znova s hodnotamy pro další iteraci, pokud (záměrně nepíši dokud) je splněna podmínka.

Hlavní šablona pro genarování tabulky se v mém skriptu jmenuje calendarWeekRowsOfMonth. Této šabloně se předá datum a ona vypíš řádek týdne, kde první vypsaný den bude právě předaný den. Tedy vypíše nejprve tolik prázdných buněk, kolikátý je to den v týdnu (k tomu slouží opět rekurzivní šablona emptyCells). Pak vypíše pomocí jiné rekurzivní šablony buňky dnů, jejichž počet je do konce týdne nebo měsíce. A na závěr, pokud den následující po právě vypsaných dnech je ještě v aktuálním měsící, zavolá sama sebe na den následující po vypsaných dnech.

Protože je XSLT a obzvláště verze 1 (kvůli funkcím via šablony) strašně ukecané, je ukázka ořezána

 

 

Vyhodnocení platnosti pravidel okna

Když už máme kostru kalendáře, zbývá naplnit buňky jednotlivých dní obsahem. Ten bude v našem případě obsahovat časová okna, která jsou v daný den k dispozici.

Jak už jsme si ukázali na začátku, v datech jsou definována pouze pravidla. Z nich se musí teprve informace o platnosti v konkrétní den dopočítat. Aby časové okno bylo v určitý den aktivní, musí být v ten den splněny všechny podmínky současně.

To lze realizovat opět pomocí rekurze tak, že otestuje jedno pravidlo a pokud je platné, rekurzivně otestustuje nasledující (pokud nějaká jsou) a vrátí výsledek. Pokud je neplatné, vrátí false a již nepokračuje.
K tomu se mohou šikovně využít klasické šablony XSLT, které se aplikují na elementy XML dokumentu. A to v tomto případě na všechny elementy pod elementem pravidla. Následující pravidla pak lze zjistit aplikováním šablon na prvky vybrané osou following-sibling.

Podobně elegantní využití XSLT ve své podstatě lze právě otestování jednotlivých pravidel. Jedoduše necháme aplikovat šablony na aktuálně vyhodnocovaný element pravidla. Aby se se aplikovala šablona provádějící vyhodnocení, stanovíme ji speciální mód evaluate. Při volání se pouze předá den a konkrétní šablona konkrétního elementu rozhodne na záladě jeho semantiky. Volající kód tak nemusí vůbec vědět o tom, co to je za pravidlo – pouze ho zajímá jestli platí nebo ne.

Vyhodnocení pravidla pak může vypadat následovně

S tímto už jen stačí v každé buňce kalendáře projít všechny definovaná okna (pomocí for-each), pro každé zjistit jestli platí a pokud ano, vypsat s pomocí přepočtu hodin začátku a konce do procent HTML blok, který pak webový prohlížeč zobrazí jako proužek odpovídající části dne :)

Výsledek

V přílohách je k dispozici ke stažení kompletní XML data a XSLT skript (včetně XSchema).

Na začátku XSLT skriptu jsou definovány hodnoty měsíce a roku, které určují, jaký kalendář se zobrazí. Samozřejmě už by jednoduše šlo například zobrazit kalendáře pro celý rok. Ale to už nechám na Vás :)

XSLT Calendar template

Action Bomberman game

Bomberman like game created as a seminar work during my computer science studies. It has multiplayer on the same computer and artificiall inteligence players.

Screenshots

ActionBombermanSnímek obrazovky (2011-11-09 14-47-08)

Features

  • Graphics from KDE granatier game
  • Multiplayer game on one keyboard
  • Multiplatform, it can be build for Windows, Linux and Mac OS
  • Computer players with artificiall inteligence.

Technologies

  • C++
  • Qt Framework
  • SVG

Project on GitHub

(Unofficial) Animated logo of Computer Graphics Group of Faculty of Math and Physics

Syntetic (programmed) animation of Computer Graphics Group logo of Faculty of Math and Physics of Charles University in Prague. Created during my computer science studies.

Task was to write source code that will handle the animation. Given were coordinates, size and colors of circles of the original 2D logo. No manual definition of keyframes was used.

Technologie

  • C#
  • OpenTK

Rekonstruktor – multiview orthographic projection to 3D

Program for reconstruction original 3D object from its orthographic projection. Demonstrates ability to automatic reconstruction, it is able to do only simple objects. Created during my computer science studies.
rekonstruktor

Features

  • Able to reconstruct original 3D object from 3 views of orthographic project of object
  • Simple and intuitive GUI
  • Easy view drawing with snapping to grid and other lines.
  • Real-time reconstructing

 Technologies

  • .NET 2
  • C#
  • WinForms

Project on GitHub

Download EXE