سامانه پشتیبانی خدمات اطلاعات

  اخبار و اعلانات

 آمار

تعداد نشریات158
تعداد شماره‌ها6,225
تعداد مقالات67,685
تعداد مشاهده مقاله114,986,571
تعداد دریافت فایل اصل مقاله89,657,626
Saberifar, Fatemehzahra, Mohades, Ali, Razzazi, Mohammadreza, J. M. O'Kane, Jason. (1397). Improper Filter Reduction. , 50(1), 69-99. doi: 10.22059/jac.2018.68340
Fatemehzahra Saberifar; Ali Mohades; Mohammadreza Razzazi; Jason J. M. O'Kane. "Improper Filter Reduction". , 50, 1, 1397, 69-99. doi: 10.22059/jac.2018.68340
Saberifar, Fatemehzahra, Mohades, Ali, Razzazi, Mohammadreza, J. M. O'Kane, Jason. (1397). 'Improper Filter Reduction', , 50(1), pp. 69-99. doi: 10.22059/jac.2018.68340
Saberifar, Fatemehzahra, Mohades, Ali, Razzazi, Mohammadreza, J. M. O'Kane, Jason. Improper Filter Reduction. , 1397; 50(1): 69-99. doi: 10.22059/jac.2018.68340

Improper Filter Reduction

Journal of Algorithms and Computation
مقاله 4، دوره 50، شماره 1، شهریور 2018، صفحه 69-99    اصل مقاله (438.53 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22059/jac.2018.68340
نویسندگان
Fatemehzahra Saberifar1؛ Ali Mohades* 2؛ Mohammadreza Razzazi2؛ Jason J. M. O'Kane3
1Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran.
2Amirkabir University of Technology
3University of South Carolina
چکیده
Combinatorial filters, which are discrete representations of estimation
processes, have been the subject of increasing interest from the robotics
community in recent years.
%
This paper considers automatic reduction of combinatorial filters to a given
size, even if that reduction necessitates changes to the filter's behavior.
%
We introduce an algorithmic problem called \emph{improper
 filter reduction}, in which the input is a combinatorial filter $F$ along
with an integer $k$ representing the target size.  The output is another
combinatorial filter $F'$ with at most $k$ states, such that the difference
in behavior between $F$ and $F'$ is minimal.
We present two methods for measuring the distance between pairs of filters, describe dynamic
programming algorithms for computing these distances, and
show that improper filter reduction is NP-hard under these methods.
%
We then describe two heuristic algorithms for improper filter reduction, one
\changed{greedy sequential} approach, and one randomized global approach based on prior work
on weighted improper graph coloring.  We have implemented these algorithms
and analyze the results of three sets of experiments.
کلیدواژه‌ها
combinatorial filters؛ Estimation؛ automata
آمار
تعداد مشاهده مقاله: 212
تعداد دریافت فایل اصل مقاله: 122


سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب