TLPlan-C: Sürekli değişkenlerle eş zamanlı planlama ve çizelgeleme
Tlplan-C: An extended temporal planner for modeling continuous change
Yazar: SERDAR KEÇİCİ
Danışman: YRD. DOÇ. DR. SANEM SARIEL TALAY
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2010
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Planlama = Planning ; Sürekli zaman parametreleri = Continuous time parameters ; Çizelgeleme = Scheduling

Özet:
Yapay zeka konusunda son yıllarda kaydedilen gelişmeler, problem çözme algoritmalarının, kurgulanmış basit bulmacaların yanında gerçekçi problemler için de çözüm sunabilmelerini sağlamaktadır. Ancak, bir problemin çözülebilmesi için önce biçimsel olarak tanımının doğru bir şekilde yapılması gerekmektedir. Dolayısıyla, problem çözme için algoritmalar tasarlamanın yanında uygun modelleme yöntemleri konusunda geniş bir araştırma alanı oluşmuş ve bu konuda yapılan araştırmalar ile problemlerin daha gerçekçi bir şekilde temsil edilmesi sağlanmıştır.Bir etmenin gerçekçi bir problemi çözebilmesi ve karmaşık hedef durumlarına ulaşabilmesi için planlama yapması gerekmektedir. Planlama kısaca, modellenen bir problem ve problem ortamı için problem tanımında verilen kurallar göz önüne alınarak, hedefe ulaştıracak aksiyon dizisinin bulunmasıdır.Etmenler aksiyonları yürütürken bazı kaynaklara ihtiyaç duyabilirler. Buna bağlı olarak, çizelgeleme, aksiyonlara kaynak kısıtlarını ihlal etmeyecek şekilde yürütme zamanı atanması işidir.Planlama aşamasında seçilen aksiyonların kaynak atamaları, belirlenen bir amaç fonksiyonunu eniyileyecek şekilde yapılır. Özellikle kaynak kısıtlarının bulunduğu problemlerin çözüm kalitesi hem planlamanın hem de çizelgelemenin başarımına bağlıdır. Bu konudaki genel yaklaşım, planlama ve çizelgeleme adımlarının ardı sıra yürütülmesidir. Fakat, aynı problemi çözen birbirinden farklı birçok aksiyon dizisi olabileceğinden, ve her aksiyon dizisi için farklı bir çizelgeleme yapılabileceğinden, farklı başarımlı sonuçlar elde edilebilir. Eniyi sonuçların alınabilmesi ve kaynakların etkin şekilde atanabilmesi için planlama ile çizelgelemenin eşzamanlı yürütülmesi gerekmektedir. Bu gereklilikten dolayı, geliştirilen birleştirilmiş planlama ve çizelgeleme sistemleri, aksiyon seçimi ile kaynak atamasını eş zamanlı olarak yürütür. Bu sistemler, zamanla doğrudan ilişkili olduğundan, zaman değerleriyle ilgili olan problemlerin de modellenmesi mümkündür.Eş zamanlı planlama ve çizelgeleme sistemleri, zamana bağlı olarak modellenmesi gereken değişimleri genellikle ayrık değişimler olarak modellerler. Fakat birden çok etmenin bulunduğu, değişikliklerin sürekli olduğu ve değişen değerlerin birbiriyle ilişki içerisinde bulunduğu ortamlarda, ayrık modelleme ile geçerli bir çözüm oluşturulamayabilir.Bu çalışmada, zamanla ilgili kısıtların ele alınabilmesi için birleşik bir planlama ve çizelgeleme sistemi kullanılarak, ayrık değişimlerle birlikte sürekli değişimleri de göz önüne alan bir model önerilmiş ve bu modeli kullanarak paylaşılan kaynak kısıtları içeren problemleri çözecek bir planlayıcı geliştirilmiştir. Bu planlayıcı literatürde Tlplan olarak önerilmiş planlayıcı sistemine bir takım iyileştirmeler eklenerek geliştirilmiştir. Geliştirilen TLPlan-C sisteminde, karmaşık kaynakların temsilinin önerilen süreklilik modeli yardımıyla yapılması sağlanmıştır. TLPlan-C zaman kısıtlarının bulunduğu, sürekliliğin modellenmesinin gerekli olduğu problemlerde eniyi çözümleri oluşturmaktadır.

Abstract:
Recent advancements in artificial intelligence research enable reasoning methods to solve real world problems as well as trivial problems. However, in order to solve a realistic problem efficiently, a correct formal representation of the problem is needed. Therefore, new problem respresentation techniques are also under research to model realistic problem constraints.An agent constructs a plan to achieve its goals in a complex problem domain. Briefly, planning is finding a sequence of actions to reach a goal state from an initial state by considering the defined rules in the domain definition.Agents may also require some resources while executing actions in a constructed plan. Accordingly, scheduling is the process of assigning start times to the actions, so that all resource constraints in the domain definition are met.An objective function is optimized when the resource assignments are made in the scheduling process. The overall solution quality for resource-constrainted problems depends on the performance of both planning and scheduling processes. Traditionally, ?first plan, and then schedule? approach is employed as two consequtive processes. However, the quality of the solution may be affected by both the selected sequence of actions and the schedule of this sequence. Planning and scheduling should be integrated in order to assign the resources effectively and find optimal solutions. Integrated planning and scheduling systems simulatenously select actions and assign resources. As these systems also deal with time, they are able to solve problems involving temporal constaints.Existing integrated planning and scheduling systems model time-dependent changes as discrete effects. However, these models are not adequate to generate a valid solution for problems with shared resources and multiple agents, where changes are continuous and interrelated.In this thesis, a novel realistic continuous planning model to handle temporal constraints is proposed, and an integrated planning and scheduling system, TLPlan-C, is developed. TLPlan-C has been developed as an extension to an existing temporal planner, TLPlan. This integrated system models continuous changes as well as discrete changes in planning problems. TLPlan-C generates optimal solutions for the problems that have complex resource constraints for which continuous changes should be modeled.