Advanced Timetabling Solutions
English
ATS4 O nas ATS4 ATS4 ATS4 Badania ATS4 Sklep ATS4 Download ATS4 Wydarzenia
Strona główna Mapa Kontakt

Jeżeli interesuje Cię więcej szczegółów na temat ATS4, skontaktuj się z nami. kontakt

Wyślij do nas E-mail
z zapytaniem.

Badania naukowe w zakresie problematyki układania planów zajęć

ATS4 na tle historycznym

Układanie planów zajęć wymaga w skali globalnej ogromnego nakładu pracy osób zajmujących się tym żmudnym zajęciem. Dlatego od wielu lat problematyka związana z usprawnieniem układania planów interesuje naukowców. Starają się oni opracować uniwersalne metody, dzięki którym plany zajęć można ułożyć sprawniej i lepiej oraz wielokrotnie je aktualizować.

Już w roku 1967 roku na Uniwersytecie w Nottingham został opisany i wdrożony jeden z pierwszych systemów planowania egzaminów oparty o metodę sekwencyjną. Później uniwersytet ten stał się centrum badawczym w tym zakresie i rozwinął się tam silny zespół naukowy pracujący pod kierownictwem prof. E.K. Burke.

W latach późniejszych pojawiają się publikacje o zastosowaniach nowych metod rozwiązywania planów zajęć takich jak: symulowane wyżarzanie, algorytmy genetyczne, poszukiwanie tabu. Natomiast w latach 90 zaczyna się stosować niezwykle efektywne metody do rozwiązywania tego typu problemów nazywane programowaniem z ograniczeniami (Constrain Programming).

W związku z tym, że wiele publikacji o problemach automatycznego układania planów zajęć pojawiały się na różnych konferencjach, które poświęcone były zagadnieniom m.in.: Sztucznej Inteligencji i Badań Operacyjnych, prof. Burke postanowił w 1995 r. zorganizować pierwszą konferencje PATAT (Practice And Theory of Automated Timetabling) poświęconą wyłącznie temu zagadnieniu. Konferencja ta miała do tej pory już 4 edycji, przy czym ostatnia z nich w 2002 r. zgromadziła ponad 100 naukowców. Najlepsze artykuły z tej konferencji są publikowane przez znaczące wydawnictwo Springer.

Przytoczone fakty pokazują, że problem układania planów zajęć nie jest problemem banalnym, który zleca się sekretarce. Jest to niejednokrotnie złożony problem kombinatoryczny, którym zajmuje się kilka ośrodków naukowych, gdzie łamią sobie nad tym głowę całe zespoły naukowców.

Geneza ATS4

W Polsce, już w latach siedemdziesiątych, na Politechnice Śląskiej w Gliwicach ówczesny rektor prof. Antoni Niederliński stwierdził, że problem planowania zajęć trzeba sformułować jako problem naukowy. Zaletą tego podejścia było to, że łatwiej było znaleźć na uczelni ludzi do rozwiązania zadania naukowego niż do wykonywania żmudnej pracy urzędniczej, której wszyscy pracownicy naukowi unikają jak ognia. Wiadomo, że pracownicy naukowo zaangażowani w tej problematyce podejdą do tego problemu z większym zapałem i w końcu ziszczą się marzenia o lepiej ułożonych planach zajęć. Wtedy do rozwiązywania tego zadania skorzystano z dostępnych komputerów ODRA, kompilatora języka Cobol dla programów kodowanych na kartach perforowanych. Starano się wykorzystać metody związane z kolorowaniem grafów. Okazało się jednak, że problem jest zbyt złożony, by można było go sensownie rozwiązywać, używając dostępnego w tych czasach sprzętu komputerowego.

Prof. Niederliński nie zniechęcił się jednak i po 20 latach powrócił do tego zagadnienia, gdy rozwój komputerów i języków programowania umożliwił rozwiązywanie tak złożonych problemów. Nastąpiło to w czasie, gdy jego zainteresowania koncentrowały się na Programowaniu w Logice z Ograniczeniami, które wyrosło z Programowania w Logice, z wykorzystaniem języka Prolog. Wtedy to pierwsi dyplomanci Profesora używali CHIP-a (Constraint Handling in Prolog), jako narzędzia do Programowania w Logice z Ograniczeniami (Constraint Logic Programming). Prace badawcze w tym kierunku ruszyły pełną parą, gdy automatyczne układanie planów zajęć stało się przedmiotem rozprawy doktorskiej Wojciecha Legierskiego - czterokrotnego zdobywcy nagrody dziekana dla najlepszego studenta na roku kierunku Automatyka i Robotyka.

Prace nad doktoratem rozpoczęły się w 2001 r. w ramach subsydium Fundacji Nauki Polskiej. Już po roku ich wyniki zostały opublikowane na wspomnianej konferencji PATAT '02, a artykuł został uznany za znaczący i opublikowany przez wydawnictwo Springer. Warto wspomnieć, że choć kilka ośrodków naukowych zajmuje się w Polsce tą problematyką, to do tej pory jedynie Politechnika Śląska może pochwalić się takim osiągnięciem.

Metody Modułu ATS4 Solver

W procedurach układania planów zajęć wykorzystano metody Programowania
z Ograniczeniami, odchodząc od klasycznej logiki i związanego z nią języka Prolog. Dzięki temu udało się wzbogacić automat o uwzględnianie ograniczeń miękkich oraz specjalny system poszukiwania rozwiązania bazujący na poszukiwaniu lokalnym (ang. Local Search). Chodzi o to, że wprowadzając ograniczenia miękkie, czyli takie, które powinny, ale nie muszą być spełnione, wprowadza się dodatkowo problem optymalizacji. Taki problem można efektywnie rozwiązać za pomocą poszukiwania lokalnego polegającego na dążeniu do coraz lepszego rezultatu poprzez kolejne niewielkie zmiany.

Procedury do automatycznego rozwiązywania planów zajęć obecnie stosowanych
w projekcie ATS4 wykorzystują również interesujące wyniki prac badawczych niezwykle zdolnego studenta Uniwersytetu Warszawskiego - Pawła Parysa. Warto wspomnieć, że po maturze zdobył on I miejsce na krajowej olimpiadzie informatycznej, a następnie uzyskał 2 miejsce na szczeblu międzynarodowym. Zwyciężył również na szczeblu krajowym w olimpiadzie matematycznej.

Do tego projektu zostali więc zaangażowani najlepsi krajowi naukowcy w tej dziedzinie, jest więc duża szansa, że tak trudny i złożony problem, jak układanie planów zajęć, będzie rozwiązany najlepiej, jak to tylko możliwe.

ATS4 jako platforma współpracy

Problem planowania zajęć jest niezwykle złożony i nadal jest wiele zagadnień, które wymagają dogłębnej analizy oraz wysiłku pracy naukowej. Dlatego procedurę samego automatu postanowiono oddzielić od całości systemu i udostępniać jej źródła do zastosowań nie komercyjnych, po to by inni naukowcy mogli skorzystać z uzyskanych wyników pracy. Dane, które są wymieniane z programem ATS4 Planner bazują na formacie XML, który został zaczerpnięty od Tomas'a Muller'a, przy czym dodano do niego kilka modyfikacji umożliwiających uwzględnienia dodatkowych ograniczeń. Ponadto system ATS4 umożliwia gromadzenie danych będących opisami rzeczywistych problemów pojawiających się w szkołach, w celu wprowadzenia lepszych automatycznych mechanizmów.

Studentom, dla których interesujące okaże się rozwijanie nowoczesnych metod rozwiązywania problemu planowania zajęć, proponuje się pisanie na ten temat prac magisterskich. W ten sposób ATS4 oferuje platformę wymiany doświadczeń, algorytmów i danych w zakresie rozwiązywania różnorodnych problemów związanych z planowaniem zajęć.

Otwarte zagadnienia

Problem planowania zajęć ma wiele zagadnień, które czekają na rozwiązania,
a którym zajmują się już naukowcy związani z ATS4. Są to między innymi następujące kwestie:

  • problem planowania zajęć, w których uczniowie mogą wybierać sobie poszczególne zajęcia (obecnie wybory uczniów muszą być uwzględnione na początku planowania i ręcznie trzeba narzucić ograniczenia, powodujące, żeby poszczególne zajęcia nie nakładały się na siebie);
  • problem układania terminów egzaminów;
  • problem wyjaśniania sprzeczności, tj. odpowiedzi na pytanie, dlaczego dane zagadnienie nie ma rozwiązania i co należy zmienić, by je uzyskać;
  • problem niewielkich zmian planu - ten przypadek pojawia się często, gdy mamy do czynienie z zeszłorocznym planem zajęć i chcemy go zmienić w jak najmniejszym stopniu, by pasował on do obecnych założeń.

W tym zakresie, w ramach projektu ATS4, oferujemy znakomite warunki współpracy.